input:

200
3 1
50 50
3 2
0 50 50
3 3
25 25 25 25
8 1
41 59
7 3
37 30 7 26
3 3
16 12 18 54
9 2
9 43 48
9 3
3 40 42 15
9 1
29 71
9 2
40 42 18
5 1
76 24
5 1
39 61
9 2
23 38 39
10 4
18 15 34 2 31
7 2
23 28 49
9 4
15 13 25 19 28
7 1
64 36
6 1
50 50
9 1
4 96
4 1
64 36
9 2
24 45 31
9 2
3 61 36
9 1
65 35
8 4
6 1 3...

output:

0
0
0
16
10
49
1
2
1
1
6
190
3
2
2
1
110
8
0
22
0
4
6
56
18
10
0
12
9
47
30
6
1
4
35
3
0
0
72
4
1
185
1
1
3
1
9
10
43
22
70
5
11
10
148
21
21
21
21
21
21
21
21
21
21
21
21
21
21
21
21
21
21
21
21
21
21
21
21
21
21
21
21
21
21
21
21
21
21
21
21
21
21
21
21
21
21
21
21
21
21
21
21
21
21
21
21
21
21
21...

result:

wrong answer 1st lines differ - expected: '500000004', found: '0'