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:

4
16
5
8
19
15
3
8
7
21
6
10
7
13
3
12
23
1
7
7
11
14
13
10
8
5
13
19
5
10
16
17
24
1
14
14
4
18
6
5
7
8
8
5
15
11
10
73
15
3
10
9
21
17
9
26
12
21
2
3
15
12
4
13
17
22
11
4
16
15
2
10
13
8
5
12
6
10
12
5
9
5
6
4
2
2
5
6
7
10
5
18
2
2
5
4
14
21
18
16

result:

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