2023 年上海市大学生程序设计竞赛 - 一月赛

B. Sets

单点时限: 2.0 sec

内存限制: 512 MB

Amuzi is going to play a game with sets.

Firstly, he has a set A=1,2,3,,n and 2 empty sets B and C. He will put some elements in A into B (Note that each element in A will be chosen no more than once). After that, for x,yB , he will put (xy) into C.

Amuzi doesn’t like the number 5 and 8, so he doesn’t want these two numbers to be in C.

Now Amuzi wants to maximize the size of B, can you tell him the maximum size of B?

输入格式

The first line contains one integer T(1T105) indicating the number of cases.

For the next T lines, each line contains one integer n(1n109) indicating one case.

输出格式

For each case, output one integer in one line indicating the answer.

样例

Input
3
3
6
9
Output
3
5
5