input:

100
21
1 3 3 3 2 3 3 2 2 1 3 2 1 3 2 1 1 1 3 3 3
3
3 3 1
19
1 3 1 1 3 3 1 3 2 3 2 2 3 3 1 1 2 2 2
10
2 2 3 1 5 2 2 5 5 3
8
1 3 3 1 3 2 3 1
3
1 2 1
27
1 1 1 2 1 3 1 2 2 3 3 3 1 1 1 1 2 1 2 2 2 2 3 2 1 3 2
4
5 1 2 2
23
2 1 3 2 3 2 2 3 1 2 1 3 1 2 3 1 3 1 2 2 2 1 1
10
4 3 5 4 5 4 1 4 3 4
8
1 2 1 3 2 3 ...

output:

3
18
6
7
19
12
3
8
7
20
5
10
6
10
3
10
16
1
5
6
10
14
13
8
8
5
13
15
5
10
16
15
10
1
10
4
4
16
6
4
7
8
7
5
13
11
10
11
15
3
10
8
19
16
8
25
12
21
2
3
15
12
4
12
17
22
11
5
14
15
2
9
12
7
3
9
4
9
11
2
2
5
6
4
2
2
4
6
7
10
3
14
2
1
5
4
10
13
14
16

result:

wrong answer 2nd lines differ - expected: '15', found: '18'