题中题

题号：NC205833
时间限制：C/C++/Rust/Pascal 2秒，其他语言4秒
空间限制：C/C++/Rust/Pascal 128 M，其他语言256 M
64bit IO Format: %lld

题目描述

ある日（有一天），ACoder在刷题，他浏览到这样一道题：

给定多项式幂级数：

$A(x) = (x+x^2)^0 + (x+x^2)^1 + (x+x^2)^2 + \dots$

请求出其 $x^n$ 项的系数在模p意义下的值。

ACoder发现，当p定下来的时候，这个题的答案随着n的增大而呈现出周期性的变化。

换句话说，当p确定的时候，如果输入是n，输出是f(n)，那么数列 $f(1),f(2),f(3),\dots$ 呈现出周期性变化，现在请你求出这个最小正周期。

特别地，p的所有质因数大小都不超过1000。

输入描述:

输入第一行是一个正整数，表示测试数据组数

接下来T行，每行包含一个正整数

输出描述:

输出T行，依次表示每组测试数据的答案

示例1

输入

复制

1
2

输出

复制

说明

p=2的时候，这个数列是，最小正周期是3，循环的部分是1,0,1