Given a bipartite graph having $$N$$ vertices in each part and $$M$$ edges, find the number of perfect matchings in it modulo $$4$$.
First line consists of a single integer $$T$$ denoting the number of test cases.
First line of each case consists of two space separated integers denoting $$N$$ and $$M$$.
Each of the following $$M$$ lines consists of two space separated integers $$u$$ and $$v$$, denoting that there is an edge between vertex numbered $$u$$ on the left side and vertex numbered $$v$$ on the right side. Vertices on each side are enumerated independently starting from $$0$$.
For each test case, print a single number in a new line - number of perfect matchings modulo $$4$$
$$1 \le T \le 10$$
$$1 \le N \le 50$$
$$0 \le M \le N * N$$
$$0 \le u, v \le N-1$$