Although Nayra doesn't like stories of random arrays as a birthday present. But on her last birthday, she got one such array as a birthday present. After struggling for a day to figure out what to do with this array. She asked Aryan for help. He gave him this problem.

Formally, you are given an array A of N numbers. Let S be the set of XOR of all possible subsets of A.
Find count of distinct numbers in S which have an odd number of bits on. Similarly, find the count of distinct numbers in S which have an even number of bits on.
Since this count can be a very large report it modulo 998244353.

Subtasks

1. 30 points: \(0 \le A_i < 2^{60}\)
2. 70 points: \(0 \le A_i < 2^{250}\)

Input format

• The first line contains T \((1 \le T \le 20)\) denoting the number of test cases.
• The first line of each test case contains two integers N \((1 \le N \le 10^3)\) and M \((1 \le M \le 250)\).
• Each of the next N lines of each test case contains a binary string of length M denoting A's elements.

Output format

• For each test case print two integers in a single line,
• The first integer should be the number of distinct numbers in S with an odd number of bits on modulo 998244353.
• The second integer should be the number of distinct numbers in S with an even number of bits on modulo 998244353.

Constraints

\(1 \le N \le 1000\)

\(1 \le T \le 20\)

All elements of the array will be given in the binary form.

Note

A bitwise XOR (⊕ operator) takes two-bit integers of equal length and performs the logical xor operation on each pair of corresponding bits. The result in each position is 1 if only the first bit is 1 or only the second bit is 1 but will be 0 if both are 0 or both are 1. You can read more about bitwise XOR operation here.

XOR of a subset B = {B_1, B_2, ...., B_k} is B_1 ⊕ B_2 ⊕ ... ⊕ B_k.