Description

Please read the description of the problem ˇ°Love Me, Love My Permutationˇ± carefully before you try to solve this problem.

Given a permutation of n(its elements range from 0 to n-1, For example: n=4,one of the permutation is 2310)you should find out how many confusion Matrixes exist such that base on any of these matrixes, no matter how you do the swap function on the permutation (only do the swap operation once), its confusion value does not increase.

Besides, find out the lexicographic smallest matrix satisfies the condition. (Given two matrixes A and B, we can get their lexicographic order by the following way: firstly, we transform A into a string A1 by simply scanning it from the left to right, from up to down. Using the same way, we transform B into a string B1, A is lexicographic smaller than B if and only if A1 is lexicographic smaller than B1, For example:

A=
[  0 0 1
   1 0 1
   0 0 0
]
B=
[    0 1 1
     0 0 1
     0 0 0
]
We tranfrom A into string A1 = 001101000, B into string B1 = 011001000, as A1 is lexicographic smaller than B1, So A is lexicographic smaller than B.)

Note again, the confusion matrix contains only 0 and 1, and it satisfies mat[i][i] is 0 (0 <= i < n) and mat[i][j] + mat[j][i] = 1 (0 <= i < n, 0 <= j < n, i != j)

Input

The first line is the number of cases T (1 <= T <= 10), then each case begins with a integer n (2 <= n <= 100), and the next line forms the description of the permutation (see the sample input).

Output

For each case, if there is no matrix which satisfies the condition, just print one line ˇ°-1ˇ±, or else, print n+1 lines, the first line is a integer indicating the number of the matrixes satisfy the condition modulo 10007, next n line is description of the Lexicographic smallest matrix which satisfies the condition (see the sample output).

Sample Input

1
2
0 1

Sample Output

1
0 1
0 0

Author

zsasuke