BrotherK likes playing GALGAME, now he wants to design a GALGAME.
Ery has designed $N$ roles for his game, each role can be described as four integers: name, face, character, magic(Just a special parameter, don't care about it). BrotherK need to select some roles for his game, and there are some rules:
Assume BrotherK has selected $K$ roles, i-th role's magic is $M_i$, the equation should be hold: $M_1~xor~M_2~xor~..~xor~M_K~=~0$. (xor means exclusive or, (a xor b) means (a ^ b) in C/C++/Java).
There is not any pair of selected role has same face.
For each character(except there is not any role with the character), BrotherK should select at least one role with the character.
Now, BrotherK wants to know there are how many ways to choose roles.
Input
The first line contains a single integer $T$, indicating the number of test cases.
Each test case begins with one integers $N$, indicating the number of roles designed by Ery.Following $N$ lines, i-th line contains three integers
$Face_i,~Character_i$ and $Magic_i$, describing the role whose Name is i.
$T$ is about 100, in most case, $N$ is small.
$1~\le~N~\le~32$.
$1~\le~Face_i, Character_i~\le~N$.
$0~\le~Magic_i~\le~100000$.
Output
For each test, print one line.
The line contains a number indicating the number of BrotherK's ways to choose roles.
