The easy and hard versions of this problem differ only in the constraints on n. In the easy version, the sum of values of n^2 over all test cases does not exceed 10^6. Furthermore, n does not exceed 1000 in each test case .
There are 2n light bulbs arranged in a row. Each light bulb has a color from 1 to n ( exactly two light bulbs for each color ).
Initially, all light bulbs are turned off. You choose a set of light bulbs S that you initially turn on. After that, you can perform the following operations in any order any number of times:
You want to choose a set of light bulbs S that you initially turn on in such a way that by performing the described operations, you can ensure that all light bulbs are turned on.
Calculate two numbers:
Input
The first line of the input contains a single integer t (1 ≤ t ≤ 10^4) — the number of test cases. Then follow the descriptions of the test cases.The first line of each test case contains a single integer n (2 ≤ n ≤ 1000) — the number of pairs of light bulbs.The second line of each test case contains 2n integers c_1, c_2, …, c_2n (1 ≤ c_i ≤ n), where c_i is the color of the i-th light bulb. For each color from 1 to n, exactly two light bulbs have this color.Additional constraint on the input: the sum of values of n^2 over all test cases does not exceed 10^6.
Output
For each test case, output two integers: the minimum size of the set S that you initially turn on; the number of sets S of minimum size (taken modulo 998244353).