Roh has recently started working on a new project and he really enjoys working on it. The thing that annoys him, however, is that the requirements seem to keep changing continuously. Everyday, Roh's supervisor Zach comes to him with a new list of requirements that Roh must fulfill. The ever-changing requirements have frustrated Roh and he wishes for once that Zach could make up his mind.

Roh's task is simple. He must construct an array a[1 ... n] of size n, whose elements are positive integers greater than 1. Everyday Zach comes to Roh with a new set of requirements. The requirement on the i-th day is defined by a subset of indices, S_i. For any two indices x, y such that x ∈ S_i and y ∉ S_i, it is required that gcd(a[x], a[y]) = 1.

On the i-th day, Roh must construct an array of positive integers a[1 ... n] of size n, such that:

• a[i] ≥ 2 or all 1 ≤ i ≤ n.
• The array satisfies all requirements up to day i, ie. it complies with each of the sets S₁ , S₂ , S₃ , ..., S_i.

Of course, there might be many such arrays and Roh must find the array with the minimum sum of elements. Zach doesn’t have the time to go through all of Roh's work. So, he asks Roh to report only two numbers, the minimum sum of elements that Roh can achieve, and the number of valid arrays with the minimum sum.

Help Roh complete his task.

The first line contains T, the number of test cases.

The first line of each case contains two integers n, and q denoting the number of elements and the number of requirements.

It is followed by q lines. The ith line describes the set S_i. It starts with an integer k denoting the number of elements of S_i. Then k distinct integers follow S_i,1, S_i,2, S_i,3, ..., S_i,k the elements of S_i.

Constraints

• 1 ≤ T ≤ 100
• 2 ≤ n ≤ 10⁵
• 1 ≤ q ≤ 10⁵
• 1 ≤ k ≤ n
• 1 ≤ S_i,j ≤ n for all 1 ≤ j ≤ k
• All elements of a set S_i are distinct, ie. S_i,1 , S_i,2, …, S_i,k are distinct.
• Sum of n over all cases does not exceed 5 x 10⁵ .
• Sum of q over all cases does not exceed 5 x 10⁵
• The total number of elements over all sets over all test cases does not exceed 10⁶.

For each test case, print q lines. The ith line for each case should contain two space-separated integers. The first integer is the minimum sum of a valid array that fulfills all requirements upto day i. The second integer is the number of valid arrays with the minimum sum. Since the number of valid arrays can be large, print the number of valid arrays modulo 998244353.

For the first day, 2, 2, 3, 3 and 3, 3, 2, 2 are the interesting sets with the minimum sum. For the second day, 2, 2, 3, 5 and 2, 2, 5, 3 are the interesting sets with the minimum sum.