TRUTHORL - Truth Or Lie

no tags 

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


hide comments
:D: 2009-10-28 17:40:53

Bignum is needed but it's not very hard to implement here ;)

Paranoid Android: 2009-10-22 13:13:49

Do we have to implement bignum implementation or will the answer fit within 64 bit ??

Last edit: 2009-10-22 13:14:09
Luke Pebody: 2009-02-17 11:06:29

Output description is wrong. Only output "No inference" if the number of combinations is 0.


Added by:Chen Xiaohong
Date:2007-11-06
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ERL JS-RHINO NODEJS PERL6 VB.NET