题目描述

对于任意整数 $p$ 和 $q$（$q > 0$），定义 $p \mod q$ 为满足 $0 \leq r \leq q - 1$ 且 $p - r$ 能被 $q$ 整除的整数 $r$。例如：

$109 \mod 10 = 9$

$-7 \mod 3 = 2$

$-56 \mod 7 = 0$

定义一个递归函数 $\Phi$ 如下：

其中 $a, b, c, d, e, f, g, h$ 是满足 $0 < a, b, c, d, e, f, g, h \leq 1000$ 的整数。可以证明，对于任意整数 $i \geq 0$，都有 $0 \leq \Phi(i) \leq 1000$。现在，对于给定的整数 $a, b, c, d, e, f, g, h, i$（$0 < a, b, c, d, e, f, g, h, i \leq 1000$），你需要编写一个程序计算并输出

$\Phi(i)$。（提示：直接递归实现上述递推关系可能会导致程序无法在较大的 $i$ 时终止。）

输入格式

第一行包含测试用例的数量 $n$。接下来的 $n$ 行，每行包含整数序列 $a, b, c, d, e, f, g, h, i$。

输出格式

对于每个测试用例，输出 $\Phi(i)$ 的正确值。

输入样例$1$

3
1 2 3 4 5 6 7 8 9
11 12 13 14 15 16 17 18 19
321 322 323 324 325 326 327 328 329

输出样例$1$

4
0
90

来源

台湾 2004