B. Kaosar and Segments
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

There is a regular $$$n$$$-sided shape with vertices labeled from $$$1$$$ to $$$n$$$ in clockwise order.

You can add a line segment with vertices $$$i$$$ and $$$j$$$ as endpoints only if:

  • $$$|i-j| \gt 1$$$.
  • $$$\gcd(i, j) = 1$$$.

Here $$$\operatorname{gcd}$$$ denotes the greatest common divisor.

Find the max number of line segments you can add such that no two segments intersect (except possibly at their endpoints).

Input

The first line will contain a single integer $$$t$$$ $$$(1\le t \le 10^4)$$$.

Each line will contain a single integer $$$n$$$ $$$(3 \le n \le 10^5)$$$.

Output

Print the max number of line segments you can add such that no two segments intersect (except possibly at their endpoints).

Example
Input
2
3
5
Output
0
2
Note

In the first test case, you can not add any line segment.

Figure for the first test case.

In the second test case, you can add a line segment with vertices $$$1$$$ and $$$3$$$ as endpoints, and add a line segment with vertices $$$3$$$ and $$$5$$$ as endpoints. It can be proven that up to $$$2$$$ line segments can be added.

Figure for the second test case.