Hints: https://atcoder.jp/contests/arc211/editorial/14696

---

Let us call an \(A\) for which there exists a sequence \(S\) satisfying the conditions a good sequence. Let us observe the characteristics of sequences that are not good sequences.

• If \(S\) contains exactly two types of numbers that sum to \(10\), then \(A\) is not a good sequence.
  • No matter how you rearrange them, there will be a location where those two types are adjacent.
• If the number of \(5\)s in \(S\) is more than \(\left\lceil\frac{|S|}{2}\right\rceil\), then \(A\) is not a good sequence.
  • No matter how you rearrange them, \(5\)s will be adjacent.

In fact, in all other cases, there exists a sequence \(S\) satisfying the conditions. The proof of this claim will be given later.

If we accept this claim, the following algorithm is correct:

• If \(A\) is already a good sequence, output \(0\).
• Otherwise, if it is not a good sequence because the number of \(5\)s is excessive, output \(2A_5-\sum_{i=1}^{9}A_i-1\).
  • This is because adding \(2A_5-\sum_{i=1}^{9}A_i-1\) to \(A_1\) makes it a good sequence.
• Otherwise (if it is not a good sequence because it contains only two types of numbers that sum to \(10\)), output \(1\).
  • This is because adding \(1\) to \(A_5\) makes it a good sequence.

---

Finally, here is the proof that the claim is correct.

When \(S\) does not contain \(5\)

Since the sum of two identical numbers is not \(10\), we only need to consider the case where all values in \(S\) are distinct.

If sorting \(S\) in ascending order satisfies the conditions, we are done.

Otherwise, there is only one location where the sum of adjacent numbers is \(10\). It can be shown that inserting an unrelated number from either end between them satisfies the conditions.

Let’s look at an example. When \(S=(1,3,4,6)\), the conditions are not satisfied because \(4\) and \(6\) are adjacent. So, if we take \(1\) and insert it between them, we get \(S=(3,4,1,6)\), which satisfies the conditions.

When \(S\) contains \(5\)

Let’s handle the trivial special cases. When rearranging only at most two \(5\)s and a non-\(5\) number \(x\), \(S=(5,x)\) or \(S=(5,x,5)\) satisfies the conditions. With this processing, we can assume that \(S\) contains at least two non-\(5\) numbers.

Remove \(5\) from \(S\), divide it into \(\max(2,A_5-1)\) sequences satisfying the conditions, and finally separate them with \(5\). However, divided sequences must not have length \(0\) (because \(5\)s would be adjacent if length is \(0\)), but may have length \(1\).

Divide \(S\) into numbers less than \(5\) and those that are not.

A sequence consisting of numbers less than \(5\) clearly satisfies the conditions. The same is true for a sequence consisting of numbers greater than \(5\). So, we can divide them appropriately by the required amount.

Let’s look at an example here too. We will rearrange \((5,5,5,5,5,1,2,2,4,6,8)\) nicely to satisfy the conditions. To do this, we aim for a sequence of the form \(S=(5,*,5,*,5,*,5,*,5)\).

We will divide \((1,2,2,4,6,8)\) into four sequences satisfying the conditions. First, divide them by whether they are less than \(5\) or not, to get \((1,2,2,4)\) and \((6,8)\). Any division is fine; let’s try \((1,2),(2,4),(6),(8)\). Finally, separating these with \(5\), we construct \(S=(5,1,2,5,2,4,5,6,5,8,5)\). This satisfies the conditions.

Implementation Example (Python (Codon 0.19.3), 14ms)

T = int(input())

for _ in range(T):
    A = [0] + list(map(int, input().split()))
    cont = []

    for i in range(10):
        if A[i]:
            cont.append(i)

    if len(cont) == 2 and cont[0] + cont[1] == 10:
        print(1)
    else:
        print(max(0, A[5] * 2 - 1 - sum(A)))