Background

小A和小C正在私奔的路上，遇到一个前来追赶他们的特工，然而这个特工明显是个临时工，三下五除二就把特工打晕了，缴获了一部手机。小A和小C想要通过这个特工的手机获取情报，而这台手机有图案密码锁。大概由于这个特工比较健忘，手机的密码提示写了一排数字，小A根据数字滑动密码锁，却不能打开。

小C说：“是不是要换个顺序才能打开？”

小A觉得很有道理，但是这个情况数好像很多的样子，然而小A是个聪明的程序员，他有足够的信心破解这个手机图案密码。

现在小A已经知道手机图案锁是只由哪几个位置组成的,手机图案锁的解锁只能通过一笔画解决,他最多需要多少次情况就一定能够破解该图案锁的密码？每个位置必须经过，每个位置只能够被经过一次。

图案锁的组成有9个位置分别为：

1 2 3

4 5 6

7 8 9

如上图所示：

会提示你密码包含1，2，3，4，5，6，7，8，9.

   其中的一种画法如上图：5->4->2->6->7->1->9->8->3.   

经过小A多次研究，发现以下规律：

如果你还没有经过5, 然后 你连接了1, 再去连接9的话, 则会经过5.

如果你已经经过5, 然后你连接1, 再去连接9的话, 则不会在重新经过5.

同理可得1和3、4和6等也满足如上规律。

Input

有T组测试案例. 每一组测试案例的第一行输入一个整数N(1<=N<=9),表示图案锁由N个密码组成。 接下来输入N个数值，表示这N密码的位置。

Output

输出最多需要多少次便能够解锁，如果不能够解锁，请输出-1。

Sample

4
1
1
2
1 9
2 
1 5
3
1 5 9

1
-1
2
4

Limitation

1s, 1024KiB for each test case.