Seq

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

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

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