Description

小孩甲的房间里有9口特殊的闹钟（标号为’A’--’I’），都只有1根个指针和4个刻度：3点，6点，9点，12点。小孩甲还有9个开关(标号为1~9)，每个开关控制着若干个闹钟。以下以“开关号 ：控制闹钟号(多个)”的格式给出9个开关的的信息： 1 ABDE(开关1控制闹钟A,B,D,E) 2 ABC 3 BCEF 4 ADG 5 BDEFH 6 CFI 7 DEGH 8 GHI 9 EFHI 每操控第i个开关一次，那么第i个开关控制的所有闹钟的指针都将沿顺时针方向转动，每次转动90度。例如A钟当前是指向3点，B为6，C为12，D为12，那么操作开关2以后，A变成了指向6点，B为9，C为3，D不变。 现在需要解决的问题是，给定9个闹钟的初始状态，求经过至少几次操作后，它们的指针全部指向12点？(输入数据一定有解)

Input

第一行为整数T(不大于10)，表明组测试数据的组数，接下来3T行，每行3个整数；每3行描述一组测试数据，分别为9个闹钟的状态。

Output

每组测试数据对应为1行，该行描述了操作数最少的那一组使得9个闹钟全部指向12点的操作。如果有多组最少操作，那么输出字典序最小的一组。即如果最小操作数为4，同时有两组操作4 5 6 7和9 3 1 1都满足题意，那么输出 4 5 6 7 （4 5 6 7< 9 3 1 1）

Sample

Input

1
9 9 12
6 6 6
6 3 6

Output

4 5 8 9

Source: 超人