Description

一个钻石游戏是在图1所示的一个分割成数个面的六边形上进行的。在这个题目里，分隔出来的面按照图中所示方式进行标号。如果两个面公用一条边，那么成它们为相邻面。那么，偶数编号的面就有三个相邻面，奇数编号的面只有两个相邻面。在游戏进行中的任何时刻，七个面中的六个里会有一个唯一的1到6之间的数字，剩下的一个面则是空的。游戏中的一步就是将一个数字从一个面移动到一个空相邻面。

从任意开始状态出发，通过一系列移动可以让游戏的状态变成如图2、3所示之一。你的任务就是计算从开始状态出发到达图2中的状态最少需要多少步。

Input

输入包含多组测试数据。第一行包含一个整数N（0 ≤ N ≤ 5,040），测试数据的数目。接下来N行每行包含{0, 1, 2, 3, 4, 5, 6}的一个排列，描述游戏的一个开始状态。排列中的第i个数字表示标号为i − 1的面上的数字。零表示一个面是空的。

Output

对每组测试数据，输出从开始状态到达图2所示状态的最少步数。如果这是不可能的，输出“-1”。

3
1324506
2410653
0123456

10
-1
0

Source

第六届北京大学程序设计大赛暨ACM/ICPC选拔赛, wenxichang

Translator

Yingchong SITU 'frkstyc'