SP22269 PERIOD1 - Periodic function, trip 1

 考虑定义域为 $\mathbb Z$，值域为 $\mathbb R$ 的**周期函数**，记它们构成的集合为 $V$。显然由于任意两个这样的函数周期的比值都是有理数，因此对于任意 $f,g\in V$ 有 $f+g\in V$，于是 $V$ 是一个向量空间。 显然 $\dim V$ 是无限的。所以你需要求 $V$ 的一些子空间的维数。 以下我们会采用一种简化记号：我们用括号括起函数值的循环节代表函数，其中第一个数代表 $f(0)$。比如，若 $f=[2,4,7]$，那么有 $f(-1)=7,f(0)=2,f(1)=4,f(2)=7$，同理接下来 $f$ 的函数值就是 $2,4,7,2,4,7,2,4,7,\cdots$。$f$ 对应的 Python 代码为： ```python def f(x): return [2, 4, 7][x%3] # (with Python notations) # 2,4,7,2,4,7,2,4,7,2,4,7,2,4,7, ... ```

给定 $N$。令 $W$ 是最小正周期不超过 $N$ 的 $f\in V$ 组成的集合。 $W$ 中的一些函数是有联系的。比如说，$[0,2]=[0,1,0,2]+[0,1,0,0]$。对于一组 $f_1,f_2,\cdots,f_m\in V$，若**不存在**一组**不全为 $0$ 的**实数 $c_1,c_2,\cdots,c_m$，使得对于任意 $x\in\mathbb Z$，都有 $c_1f_1(x)+c_2f_2(x)+\cdots+c_mf_m(x)=0$，我们就称集合 $\{f_1,f_2,\cdots,f_m\}$ 是线性无关的。 令 $S\subseteq W$ 为一个线性无关的集合。$S$ 的大小最大是多少？

第一行一个整数 $T$，代表数据组数。 接下来 $T$ 行，每行一个正整数 $N$，代表一组数据。

输出 $T$ 行，代表 $T$ 组数据的答案。

### 数据范围 * $1\leq T\leq 100$ * $1\leq N\leq 10^8$