ヒント：https://atcoder.jp/contests/arc211/editorial/14503

---

条件を満たす数列 \(S\) が存在する \(A\) を、良い数列と呼ぶことにします。良い数列でない数列の特徴を観察しましょう。

• \(S\) に含まれる数が \(2\) 種類で、それらを足すと \(10\) になることになる場合、\(A\) は良い数列ではない。
  • どのように並べ替えても、その \(2\) 種類が隣り合う箇所が存在してしまいます。
• \(S\) のうち、\(5\) の個数が \(\left\lceil\frac{|S|}{2}\right\rceil\) 個より多くを占めることになる場合、\(A\) は良い数列ではない。
  • どのように並べ替えても、\(5\) が隣り合ってしまいます。

実は、これら以外の場合は条件を満たす数列 \(S\) が存在します。この主張の証明は後述します。

この主張を認めると、以下のアルゴリズムが正当です。

• \(A\) がすでに良い数列なら、\(0\) を出力する。
• そうでなく、\(5\) の個数が過剰であるために良い数列でないなら、\(2A_5-\sum_{i=1}^{9}A_i-1\) を出力する。
  • \(A_1\) に \(2A_5-\sum_{i=1}^{9}A_i-1\) 加算すれば良い数列となるためです。
• そうでない（和が \(10\) となる \(2\) 種類の数しか含まれないために良い数列でない）なら、\(1\) を出力する。
  • \(A_5\) に \(1\) 加算すれば良い数列となるためです。

---

最後に、主張が正しいことの証明です。

\(S\) に \(5\) が含まれない場合

同じ数を隣り合わせてもその和は \(10\) にならないので、\(S\) の値がすべて相異なる場合のみ考えればよいです。

\(S\) を昇順に並べれば条件を満たす場合はそれでよいです。

そうでない場合、隣り合う数の和が \(10\) になる箇所は \(1\) 箇所しかありません。その間に、どちらかの端から関係ない数を持ってきて挿入すれば条件を満たすことが示せます。

具体例を見てみましょう。\(S=(1,3,4,6)\) のとき、このままでは \(4\) と \(6\) が隣り合っているせいで条件を満たしません。そこで、\(1\) をとってきてその間に挿入すると \(S=(3,4,1,6)\) となって条件を満たします。

\(S\) に \(5\) が含まれる場合

自明な特殊ケースだけ処理してしまいます。\(2\) つ以下の \(5\) と \(5\) でない数 \(x\) のみを並び替える場合、\(S=(5,x)\) または \(S=(5,x,5)\) が条件を満たします。この処理により、\(S\) に含まれる \(5\) でない数は \(2\) つ以上としてよいです。

\(S\) から \(5\) を抜いて、\(\max(2,A_5-1)\) 個の条件を満たす数列に分け、最後にそれらを \(5\) で区切ればよいです。ただし、分けた数列が長さ \(0\) であることは許容せず（長さ \(0\) だと \(5\) が隣り合ってしまうためです）、長さ \(1\) であることは許容します。

\(S\) を \(5\) 未満のものとそうでないものに分けます。

\(5\) 未満の数からなる数列は明らかに条件を満たします。\(5\) より大きい数からなる数列も同様です。ですから、適当に必要量分ければよいです。

こちらも具体例を見てみましょう。\((5,5,5,5,5,1,2,2,4,6,8)\) をうまいこと並び替えて条件を満たすようにします。そのために、\(S=(5,*,5,*,5,*,5,*,5)\) の形の数列を目指すことにします。

\((1,2,2,4,6,8)\) を \(4\) 個の条件を満たす数列に分けることにします。まず \(5\) 未満かそうでないかで分けて、\((1,2,2,4)\) と \((6,8)\) とします。あとはどう分けてもいいのですが、\((1,2),(2,4),(6),(8)\) としてみます。最後にこれらを \(5\) で区切って、\(S=(5,1,2,5,2,4,5,6,5,8,5)\) が構築できました。これは条件を満たしています。

実装例 (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)))