input:

50000
10 19
12 6 1 12 11 15 4 1 13 18
10 8
8 7 6 7 6 2 2 3 4 8
10 6
3 2 6 6 5 2 3 4 5 6
10 11
6 3 7 9 2 1 2 10 10 4
10 6
6 1 2 6 1 1 3 4 2 1
10 9
8 5 3 9 1 7 5 5 1 1
10 5
1 4 3 2 5 4 5 3 5 2
10 14
3 8 12 10 4 2 3 13 7 3
10 14
5 5 12 2 8 1 13 9 8 5
10 7
5 5 6 6 1 5 3 7 3 4
10 7
5 1 4 6 1 6 4 3 7 5
10...

output:

3
5
4
4
2
3
3
7
3
3
4
5
2
3
6
6
7
3
7
6
5
5
6
2
6
8
6
2
5
5
6
1
2
2
4
5
2
3
7
3
2
5
6
1
3
3
2
3
1
4
6
6
4
7
2
4
5
3
6
6
6
3
7
3
6
3
3
4
7
6
6
7
4
3
3
4
4
6
3
3
6
6
4
5
5
9
4
5
7
5
1
5
1
2
5
6
6
8
4
3
4
5
5
3
7
4
3
2
3
3
3
5
4
4
2
6
6
4
4
5
7
4
5
7
4
7
2
7
6
6
6
5
4
2
5
4
1
3
4
4
2
6
3
5
4
3
5
6
6
6
...

result:

wrong answer 1st numbers differ - expected: '6', found: '3'