题目描述

ZC 神最擅长逻辑推理，一日，他给大家讲述起自己儿时的数字玩具。

该玩具酷似魔方，又不是魔方。具体来说，它不是一个 $3 \times 3 \times 3$ 的结构，而是 $4 \times 2$ 的结构。

按照该玩具约定的玩法，我们可反复地以如下三种方式对其做变换：

1. 交换上下两行。比如，图 $(a)$ 经此变换后结果如图 $(b)$ 所示。

2. 循环右移（ZC 神从小就懂得这是什么意思的）。比如，图 $(b)$ 经此变换后结果如图 $(c)$ 所示。

3. 中心顺时针旋转。比如，图 $(c)$ 经此变换后结果如图 $(d)$ 所示。

ZC 神自小就是这方面的天才，他往往是一只手还没揩干鼻涕，另一只手已经迅速地将处于任意状态的玩具复原至如图 $(a)$ 所示的初始状态。物质极其匮乏的当年，ZC 神只有一个这样的玩具；物质极大丰富的今天，你已拥有多个处于不同状态的玩具。现在，就请将它们全部复原吧。

输入格式

第一行是一个正整数，即你拥有的魔方玩具总数 $N$。

接下来共 $N$ 行，每行 $8$ 个正整数，是 $1\sim 8$ 的排列，表示该玩具的当前状态。

这里，魔方状态的表示规则为：前四个数自左向右给出魔方的第一行，后四个数自右向左给出第二行。比如，初始状态表示为 1 2 3 4 5 6 7 8。

输出格式

共 $N$ 行，各含一个整数，依次对应于复原各玩具所需执行变换的最少次数。

特别地，若某个玩具不可复原，则相应行输出 $-1$。

2
1 2 3 4 5 6 7 8
8 6 3 5 4 2 7 1

0
2

提示

对于 $60\%$ 的数据，$N = 1$；

对于 $100\%$ 的数据，$1 \le N \le 1,000$。