题目描述

Fruit 同学和 Siby 同学很喜欢超级奇数。

超级奇数的定义：

• 对于一个正整数，如果其十进制表示中的每一位都是奇数（即仅由 $1,3,5,7,9$ 中的某些数码组成），则定义它是一个 超级奇数。例如，$3,7,17,31,139511,975319$ 等都是超级奇数，而 $2,16,23,13365,139454,310111$ 等则不是。

有一天，他们在放学的路上想到了这样一个问题：“给定一个正整数 $a$，如何为它找到一个最小的 非负整数 $b$，使得 $a+b$ 为一个超级奇数？”

两位同学很快就想到了解法，但他们没学过编程，所以在处理大量的数据时有些力不从心。因此，他们找到了学习算法竞赛的你，希望你能用计算机快速地解答这个问题。

输入格式

每个测试点包含多组测试数据，各组测试数据之间相互独立。

第一行包含一个正整数 $T$，表示测试数据的组数。

对于每组测试数据：仅输入一行，包含一个正整数 $a$。

输出格式

对于每组测试数据：仅需在单独一行输出一个非负整数，表示 $b$ 的最小值。

3
7
16
23

0
1
8

8
2
82
128
136
13365
139454
310111
975319

1
9
3
1
6
57
1000
0

提示

【样例 #1】

对于第一组测试数据：

• 显然，$7$ 本身就是一个超级奇数，所以当 $a=7$ 时，只需取 $b=0$ 就能使得 $a+b$ 为超级奇数。
• 综上，$b$ 的最小值为 $0$。

对于第二组测试数据：

• 当 $b=0$ 时，$a+b=16$，含有偶数数码 $6$，不是超级奇数；
• 当 $b=1$ 时，$a+b=17$，仅含有奇数数码，是超级奇数。
• 综上，$b$ 的最小值为 $1$。

对于第三组测试数据：

• 当 $b=0$ 时，$a+b=23$，含有偶数数码 $2$，不是超级奇数；
• 当 $b=1$ 时，$a+b=24$，含有偶数数码 $2,4$，不是超级奇数；
• 当 $b=2$ 时，$a+b=25$，含有偶数数码 $2$，不是超级奇数；
• 以此类推，当 $0 \le b \le 7$ 时，验证知 $a+b$ 均不是超级奇数；
• 当 $b=8$ 时，$a+b=31$，仅含有奇数数码，是超级奇数。
• 综上，$b$ 的最小值为 $8$。

【数据范围】

对于所有测试点，保证 $1\le T\le 2\times 10^3$，$1 \le a\le {10}^{12}$。

特殊性质 A：保证在 $a$ 的十进制表示中，有且仅有一位是偶数（如 $99\blue{4}75$，$1357\blue{8}$ 等，其中标蓝的为偶数数码）。