L. Growing Letters
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output
Every day, we grow, learn, and overcome challenges.
— The Secret Partner

Just like us, letters grow too.

Define $$$F_0 = \mbox{"a"}; F_i = F_{i-1} + \mbox{"b"} + F_{i-1}$$$ for all $$$i \ge 1$$$.

For example, $$$F_1 = F_0 + \mbox{"b"} + F_0 = \mbox{"aba"}$$$.

You are given a string $$$S$$$, but since it can be very large, it is described as an array $$$a$$$ of $$$n$$$ integers, where $$$S = F_{a_1} + F_{a_2} + ... + F_{a_n}$$$.

For example, for $$$a = \{1, 0, 0\}, S = \mbox{"aba" + "a" + "a" = "abaaa"}$$$.

The letters in $$$S$$$ merge and grow together. This is done as follows:

  1. Find the least $$$i$$$ such that $$$S_i = S_{i+1}$$$. If no such $$$i$$$ exists, the growing process is complete.
  2. $$$S_i$$$ is set to the next letter of the alphabet. In case $$$S_i = \mbox{'z'}$$$, It is set to $$$\mbox{'a'}$$$.
  3. $$$S_{i+1}$$$ is erased.
  4. Repeat.

For example, for $$$S = \mbox{"abaaaaba"}$$$, the growing process goes as follows:

$$$\mbox{ab(aa)aaba} \rightarrow \mbox{ab(b)aaba}$$$

$$$\mbox{a(bb)aaba} \rightarrow \mbox{a(c)aaba}$$$

$$$\mbox{ac(aa)ba} \rightarrow \mbox{ac(b)ba}$$$

$$$\mbox{ac(bb)a} \rightarrow \mbox{ac(c)a}$$$

$$$\mbox{a(cc)a} \rightarrow \mbox{a(d)a}$$$

Can you find the size of $$$S$$$ after the growing process is complete?

Input

Each test contains multiple test cases. The first line contains the number of test cases $$$t$$$ $$$(1 \le t \le 10^4)$$$. The description of the test cases follows.

The first line of each test case contains a single integer $$$n$$$ $$$(1 \le n \le 10^5)$$$ – The size of the array.

The second line of each test case contains $$$n$$$ integers $$$a_1, a_2, ..., a_n$$$ $$$(0 \le a_i \le 15)$$$ – The elements of the array.

It is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$10^5$$$

Output

For each test case, output a single integer, the size of $$$S$$$ after the growing process.

Example
Input
3
4
1 0 0 1
8
0 0 0 0 0 0 0 0
3
0 3 0
Output
3
1
13
Note

The first test case is described in the example in the statement.

In the second test case, $$$S = \mbox{"aaaaaaaa"}$$$. It grows into $$$\mbox{"d"}$$$.