問題

背景

注意力散漫なビッグブリッジ伯爵はよく電話番号を書き間違えて大学の事務局に怒られている。何回も怒られてさすがに懲りた彼は、自分の書き間違えの傾向を調べた結果、隣接する 2 つの数字を入れ替えて書いてしまうことが非常に多いことがわかった。このミスを犯した時に彼がすぐに気がつけるよう、簡単に計算できる検査符号を設計してあげよう。

課題

10 桁の整数に対するチェックディジットを設計せよ。すなわち、次に示す 2 つの条件を満たす、10 桁の整数を入力とし 0 以上 100 未満の整数であるチェックディジットを出力する関数を設計せよ。ただし、入力の整数は 0 以上で、10^9 未満の整数についてはleading zeroを付けて、10 桁と見なす。

• 同一の入力に対して常に同じ出力を得る。
• 隣接する 2 数が異なる時、それを入れ替えて得た整数を入力とすると、元と異なる出力を得る。

配点

200

入力

入力は以下の形式で与えられる。

T
a_1
:
a_T

1 行目にはチェックディジットをつける整数の個数 T が与えられる。 続く T 行にはチェックディジットをつける整数 a_i が 1 行ずつ与えられる。

制約

• 1 ≦ T ≦ 10^5
• a_i は 0 以上 10^{10} 未満の整数で、10 桁になるようにleading zeroが付けられている。
• a の要素は重複しうる、すなわち、i ≠ j である i, j に対して a_i = a_j となることがあることに注意せよ。

出力

入力で与えられたそれぞれの整数に対応するチェックディジットを出力せよ。

採点方式

この問題に対しては 8 つのテストケースが用意されており、それぞれ 25 点を満点として採点される。

それぞれのテストケースにおける T の値は次の通り。

• T = 30, 100, 300, 1000, 3000, 10000, 30000, 100000

各テストケースに対するジャッジの出力は次のようにして定める。

• つけたチェックディジットが問題文に示す2つの条件と矛盾するとき - WA
• つけたチェックディジットが問題文に示す2つの条件に矛盾しないとき - AC
• この時の得点は、出力に含まれるチェックディジットの種類数を k として、 min(25, max(8 - k, 0)^2) とする。

各テストケースは独立に採点される。特に、同じ整数値に対して異なるテストケースで異なるチェックディジットが付けられていてもただちに WA とはならない。

入力例1

6
0000000011
0000000012
0000000013
0000000021
0000000031
0000000011

出力例1

0
0
0
1
1
0