SP13913 MANGOES - Real Mangoes for Ranjith

Ranjith 对芒果情有独钟，某个阳光明媚的日子，他去市场买芒果。在市场中，他发现面前有 $N$ 个箱子（编号从 $1$ 到 $N$），每个箱子中都装满了芒果。编号为 $i$ 的箱子 $b_i$ 中恰好有 $i$ 个芒果，也就是说，$b_i$ 中芒果的数量是 $m_i = i$。箱子 $b_i$ 中芒果的类型记为 $t_i$，可能是「真」芒果，也可能是「假」芒果。他可以选择任何一个编号不超过 $N-2$ 的箱子，但他无法知道该箱子中芒果的真假。 箱子 $b_i$ 的芒果类型取决于三连箱 $b_i$、$b_{i+1}$ 和 $b_{i+2}$ 中芒果的数量，即 $\{m_i, m_{i+1}, m_{i+2}\}$。如果从这个集合里任取两个数，其最大公约数（GCD）都为 $1$，那么 $b_i$ 中的芒果是「真」的；否则为「假」的。特别地，对于 $i = N-1$ 和 $i = N$，箱子 $t_i$ 的类型默认是「假」。 现在，给定一个整数 $N$，Ranjith 想知道他能从所有箱子中买到的「真」芒果的总数。由于 Ranjith 无法处理超过 $N$ 的数，请输出结果对 $N$ 取模后的值。

第一行是测试用例的数量 $T$； 接下来的 $T$ 行中，每行包含一个整数 $N$，表示箱子的数量。

输出 $T$ 行，每行表示对应测试用例中 Ranjith 能得到的「真」芒果总数（取模 $N$ 后的结果）。

- $1 \leq T \leq 10^5$ - $3 \leq N \leq 10^9$ **本翻译由 AI 自动生成**