Suppose you have m yes or no questions that you want to ask n people. You are allowed to ask each person exactly two different questions. He/she will answer exactly one of them correctly and one of them incorrectly, you don't know which is a correct answer and which is an incorrect one. Given their answers, determine the number of combinations of answers to the m questions that can still be correct (i.e., no contradictions).

Input

First line is the number of inputs. For each set of input, start out with a line of n<=10000 and m<=200, followed by n lines. The i-th line has four integers a b c d. It means that the answer given by the i-th person for question a is b, and for question c is d. Moreover, the answer "1" means yes, and "0" means no.

Output

For each line of input, output "No Inference" if the answers do not help you eliminate any wrong combination of answers or the number of combinations of possible answers is 0, otherwise output the size of the set of combinations of answers still possible.

Sample

Input
2
2 2
1 1 2 0
1 1 2 1
4 4
1 1 2 1
1 1 3 0
2 1 4 1
3 1 4 0

Output
No Inference
2

Problem setter --- sy