你认为特立独行（eccentric）很容易吗？如果你是一个数字，那可就不一定了。

一个 $2N$ 位的整数 $X$（可能含有前导零）的偏心度定义为：在满足对于每个数字 $d$（$0 \le d \le 9$）都有 $S_d(X) = S_d(a) + S_d(b)$ 的所有 $N$ 位整数 $a$ 和 $b$（同样可能含有前导零）中，$|a + b - 10^N|$ 的最小可能值。其中 $S_d(P)$ 表示数字 $d$ 在 $P$ 的十进制表示中出现的次数。

例如，好玩数（amusing numbers，参见题目 Counting Amusing Numbers）的偏心度等于 $0$，而 $192747$ 的偏心度等于 $7$（$|274 + 719 - 1000| = 7$）。

给你一些长度为偶数的数字。求出它们每一个的偏心度。

输入格式

输入的第一行包含测试用例的数量 $T$（$1 \le T \le 1000$）。

接下来的 $T$ 行，每行包含一个长度为偶数的整数（可能含有前导零）。

输入文件中所有数字（除 $T$ 外）的总长度不超过 $10^6$。

输出格式

对于每个测试用例，输出一行，包含输入文件中对应数字的偏心度。

样例

输入样例 1

3
9820
192747
000001

输出样例 1

0
7
900