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
15
3
7
20
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
14
10
1
10
4
3
16
5
4
7
8
7
5
13
10
10
10
14
3
9
8
19
16
8
25
11
21
2
3
14
12
4
12
17
22
11
3
14
15
2
9
12
7
3
9
4
9
11
2
2
5
5
3
2
2
4
6
7
10
3
14
2
1
5
4
8
13
14
16

result:

wrong answer 5th lines differ - expected: '19', found: '20'