#描述#
小孩甲的房间里有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点？(输入数据一定有解)

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

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

#样例1#
##样例输入1##

1
9 9 12
6 6 6
6 3 6

##样例输出1##

4 5 8 9

#限制#
2000ms
65536KB

#提示#

#来源#
超人