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:

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

result:

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