Problem Statement

You are given a length-$9$ sequence of non-negative integers $A=(A_1,A_2,\dots,A_9)$. It is guaranteed that $2\leq \sum_{i=1}^{9}A_i$.

You can perform the following operation any number of times (possibly zero): choose one element of $A$ and add $1$ to it.

What is the minimum number of operations required so that there exists a sequence of positive integers $S$ satisfying all of the following conditions?

• All elements of $S$ are between $1$ and $9$, inclusive.
• $S$ contains exactly $A_i$ occurrences of $i$ for each integer $i$ such that $1\leq i\leq 9$. (Thus, the length of $S$ is $\sum_{i=1}^{9}A_i$.)
• No two adjacent elements sum to $10$.

It can be proved that the goal can be achieved in a finite number of operations.

You are given $T$ test cases; solve each of them.

Constraints

• $1\leq T\leq 10^3$
• $0\leq A_i\leq 10^9$ $(1\leq i\leq 9)$
• $2\leq \sum_{i=1}^{9}A_i$
• All input values are integers.

Input

The input is given from Standard Input in the following format:

T
\text{case}_1
\text{case}_2
\vdots
\text{case}_T

Each test case is given in the following format:

A_1 A_2 \dots A_9

Output

Output $T$ lines.

The $i$-th line should contain the answer for the $i$-th test case.