Cirno has prepared $$$n$$$ arrays of length $$$n$$$ each. Each array is a permutation of $$$n$$$ integers from $$$1$$$ to $$$n$$$. These arrays are special: for all $$$1 \leq i \leq n$$$, if we take the $$$i$$$-th element of each array and form another array of length $$$n$$$ with these elements, the resultant array is also a permutation of $$$n$$$ integers from $$$1$$$ to $$$n$$$. In the other words, if you put these $$$n$$$ arrays under each other to form a matrix with $$$n$$$ rows and $$$n$$$ columns, this matrix is a Latin square.

Afterwards, Cirno added additional $$$n$$$ arrays, each array is a permutation of $$$n$$$ integers from $$$1$$$ to $$$n$$$. For all $$$1 \leq i \leq n$$$, there exists at least one position $$$1 \leq k \leq n$$$, such that for the $$$i$$$-th array and the $$$(n + i)$$$-th array, the $$$k$$$-th element of both arrays is the same. Notice that the arrays indexed from $$$n + 1$$$ to $$$2n$$$ don't have to form a Latin square.

Also, Cirno made sure that for all $$$2n$$$ arrays, no two arrays are completely equal, i. e. for all pair of indices $$$1 \leq i \lt j \leq 2n$$$, there exists at least one position $$$1 \leq k \leq n$$$, such that the $$$k$$$-th elements of the $$$i$$$-th and $$$j$$$-th array are different.

Finally, Cirno arbitrarily changed the order of $$$2n$$$ arrays.

AquaMoon calls a subset of all $$$2n$$$ arrays of size $$$n$$$ good if these arrays from a Latin square.

AquaMoon wants to know how many good subsets exist. Because this number may be particularly large, find it modulo $$$998\,244\,353$$$. Also, she wants to find any good subset. Can you help her?

Input

The input consists of multiple test cases. The first line contains a single integer $$$t$$$ ($$$1 \leq t \leq 100$$$) — the number of test cases.

The first line of each test case contains a single integer $$$n$$$ ($$$5 \leq n \leq 500$$$).

Then $$$2n$$$ lines followed. The $$$i$$$-th of these lines contains $$$n$$$ integers, representing the $$$i$$$-th array.

It is guaranteed, that the sum of $$$n$$$ over all test cases does not exceed $$$500$$$.

Output

For each test case print two lines.

In the first line, print the number of good subsets by modulo $$$998\,244\,353$$$.

In the second line, print $$$n$$$ indices from $$$1$$$ to $$$2n$$$ — indices of the $$$n$$$ arrays that form a good subset (you can print them in any order). If there are several possible answers — print any of them.

Note

In the first test case, the number of good subsets is $$$1$$$. The only such subset is the set of arrays with indices $$$1$$$, $$$2$$$, $$$3$$$, $$$4$$$, $$$5$$$, $$$6$$$, $$$7$$$.

In the second test case, the number of good subsets is $$$2$$$. They are $$$1$$$, $$$3$$$, $$$5$$$, $$$6$$$, $$$10$$$ or $$$2$$$, $$$4$$$, $$$7$$$, $$$8$$$, $$$9$$$.

✓	#	Name		✎	Rating↕	Solved↕
	1651E	Sum of Matchings brute force combinatorics constructive algorithms dfs and similar graph matchings greedy math			2600	669
	1545C	AquaMoon and Permutations 2-sat brute force combinatorics constructive algorithms graph matchings graphs			2800	797

Problemset