Alice and Bob are extremely happy recently. Because the school assigns a new machine room to their lab. They are in charge of setting up a group of servers. In the room, there are N * N blanks to put servers. Alice wants the arrangement of servers to be elegant, so she thinks that some blanks must be empty, while others must not be empty. According to the need of lab, Bob is planning to purchase K types of severs. Moreover, he gives T groups of blanks, where one blank might be contained in different groups. Each group has exactly K blanks, and any two of servers in the blanks of one group must not be the same type. Now, some servers has been put in some blank, which can not be changed. With all these conditions, Alice and Bob want to know how many ways that they can arrange the machine room.
输入描述:
The first line is the number of test cases.
For each test case, the first line consists of three integers N, K, and T (N, K ≤ 6, T≤ 12).
In the next N lines, each line consists of N integers Ai,j.If Ai,j = -1, the blank (i, j) must be empty. If Ai,j = 0, a server is require to put on this blank. Otherwise, a server of type Ai,j is on this blank.
In the next T lines, each line consists of K pair of integers. Each pair of integers donate the coordinate of blank in this group.
输出描述:
For each test case, output an integer donating the ways that Alice and Bob can arrange the room. If the solution is larger than 20172017, output `TOO MANY`.
示例1
输入
复制
2
3 3 4
0 0 1
0 -1 0
0 0 0
1 1 1 2 1 3
1 1 2 1 3 1
1 3 2 3 3 3
3 1 3 2 3 3
5 5 0
0 0 0 0 0
0 0 0 0 0
0 0 0 0 0
0 0 0 0 0
0 0 0 0 0