A. 社团招新
time limit per test
30 s
memory limit per test
128 megabytes
input
standard input
output
standard output

计网院里面有n个学生。

他们中任意一些人都可以成立一个社团。

如果社团满足3男有1女，就可以一对情侣一对基。

但是院里要求这些社团有如下要求：

  • 为方便社团决议（少数服从多数），每个社团里面只有奇数个成员；
  • 为方便社团联谊，每两个社团的共同成员是偶数。

现在，计网院的海王哥哥想要知道最多可以成立几个社团。

Input

第一行是一个整数T (1 ≤ T ≤ 200000)，表示样例的个数。 以后每行一个样例，为一个整数n (3 ≤ n ≤ 1000000)。

Output

每行输出一个样例的结果。

Example
Input
1
3
Output
3