The annual Dragon Jousting Tournament has begun!
There are $2^N$ number of contestants with each one labelled from $1$ to $2^N$.

The tournament is in the format of a single elimination bracket with $N$ rounds.
On each round, the remaining contestants form groups of two from left to right to form a match.
The winner of a match is determined purely by chance.

However, King Loong decided to increase the popularity of the tournament by rigging it!
He decides to implement $T$ rigging strategies.
In each strategy, he cherry picks $M$ pairs of contestants $(B_{i,0},B_{i,1})$ and wants $B_{i,0}$ to win $B_{i,1}$ in a match.
He realized this is no easy task, and asks his servant (You) to determine whether there exists a pairing for each strategy where it is possible to satisify all the requests.

Input

The first line of input has two numbers, $T$, $N$.
On each strategy, the first line has one number $M$ and the next $M$ lines has two numbers each, representing the $M$ pairs $(B_{i,0},B_{i,1})$.

Output

Output $T$ lines, on each line output 1 if there is a valid pairing or 0 if there is no valid pairing.

Constraints

For all subtasks:
$1\le T\le 10$
$1 \le N\le 18$
$1 \le M\le 2^N-1$
$1 \le B_{i,0},B_{i,1} \le 2^N, B_{i,0} \neq B_{i,1}, (B_{i,0},B_{i,1})\neq (B_{j,0},B_{j,1})$

Subtask 1 (17%): $M = 2^N-1$
Subtask 2 (22%): $1\le N\le 3$
Subtask 3 (40%): For all but one $i$, $B_{i,0}=B_{j, 1}$ for at least one $j$
Subtask 4 (21%): No additional constraints