Description

This is a normal judge problem.

Given an empty board with L empty vertical slot numbered from 0 to L-1. There are totally R rounds in this game. At each round, arbitrary number of digits, denoted by d₁, d₂, ..., d_N will be inserted into slot l_i. After R rounds, if there exist some rows consisting of both empty space(s) and digit(s), replace all empty space(s) in the same row with 0.

Finally, you need to sum up the number in each row in base-10.

 

In this problem, each test case contains multiple cases. Each case is independent. You need to output one answer per each case.

Input

The first line contains an integer T, representing the number of cases.

The first line of each case contains two integer L and R, representing the number of vertical slots on the board and the number of rounds.

The following R lines contains N+1 integer l_i, d₁, d₂, ..., d_N, representing the inserting slot, and the N digit(s) inserted.

 

It is guaranteed that:

• 1 ≤ T ≤ 10
• 0 < L, R
• 0 ≤ l_i ≤ L-1
• 0 ≤ d_i ≤ 9
• 0 < N
• Test case #1 ~ #3: L ≤ 5, R = L, N = L
• Test case #4: L ≤ 10, R = L, N = L
• Test case #5: L ≤ 10, R ≤ 10², N ≤ 10³

Output

For each case, output the sum of the number in each row in base-10 with a new line symbol.

Sample Input and Output Explanation

Sample Input Case 1:

In the 1-st round, you insert 0, 0, and 3 into slot 0.

In the 2-nd round, you insert 0, 2, and 0 into slot 1.

In the 3-rd round, you insert 1, 0, and 0 into slot 2.

After 3 rounds, replace all empty spaces with 0. In this case, because each row only consists of empty digits (row 1 to row 3) or empty spaces (row 4 and above), there is no need to insert extra 0 into the board.

The status of the board after insertion in shown below. The answer will be 300 + 20 + 1 = 321

row 3	030	000	000
row 2	0	2	0
row 1	0	0	1
slot number	0	1	2

 

Sample Input Case 2:

In the 1-st round, you insert 0, 0, and 0 into slot 0.

In the 2-nd round, you insert 1, 2, and 3 into slot 2.

After 2 rounds, replace all empty spaces with 0.

The status of the board after insertion in shown below. The answer will be 3 + 2 + 1 = 6

row 3	000	000	030
row 2	0	0	2
row 1	0	0	1
slot number	0	1	2

 

Sample Input Case 3:

In the 1-st round, you insert 1 and 1 into slot 1.

In the 2-nd round, you insert 1, 1 and 1 into slot 2.

In the 3-rd round, you insert 1, 1, 1, and 1 into slot 3.

After 3 rounds, replace all empty spaces with 0.

The status of the board after insertion in shown below. The answer will be 1 + 11 + 111 + 111 = 234

row 4	000	0	0	010
row 3	0	0	1	1
row 2	0	010	010	1
row 1	0	1	1	1
slot number	0	1	2	3

 

Hint

1. What is the maximum number of inserted digits in a slot? That is, what is the maximum number of rows on the board? You may need to refer to the input constraints.

2. Do you really need to insert 0 after R rounds finish?

3. For test case #5, because the number of inserted digits N is unknown, you can use "stringstream" library to handle this kind of input.

Sample Input  Download

Sample Output  Download

Tags

Discuss