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:

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

result:

wrong answer 1st lines differ - expected: '3', found: '2'