Problem Description

度度熊有一个递推式 $a_{n} = (\sum_{i=1}^{n-1} a_{i}*i) \% n$
其中 $a_1 = 1$。现给出 $n$，需要求 $a_n$。

Input

第一行输入一个整数 $T$，代表 $T~(1 \leq T \leq 100000$) 组数据。
接下 $T$ 行，每行一个数字 $n~(1\leq n \leq 10^{12})$。

Output

输出 $T$ 行，每行一个整数表示答案。

5
1
2
3
4
5

1
1
0
3
0