#P1201. 九的余数

九的余数

现在给你一个自然数n,它的位数小于等于一百万,现在你要做的就是求出这个数整除九之后的余数。

Input

第一行有一个整数m(1<=m<=8),表示有m组测试数据;
随后m行每行有一个自然数n。

Output

输出n整除九之后的余数,每次输出占一行。

Sample Input

3
4
5
465456541

Sample Output

4
5
4

HINT

Source