D. Search For Beauty
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

Kalu has an integer number $$$N$$$. He defines the beauty of a number $$$k$$$ as follows:

If $$$k$$$ and $$$N$$$ are co-prime, the beauty of $$$k$$$ is $$$GCD(k−1,N)$$$. Otherwise, the beauty is $$$0$$$.

Kalu wants to find the sum of beauty for all integers $$$k$$$, such that $$$1 \le k \le N$$$.

However, Kalu is busy, so he asked you to write a program to help him with his task.

Notes

  • $$$GCD(a,\, b)$$$, the greatest common divisor of two integers $$$a$$$ and $$$b$$$, is the largest positive integer that divides both $$$a$$$ and $$$b$$$ without leaving a remainder.
  • Two numbers are co-prime if their greatest common divisor ($$$GCD$$$) is $$$1$$$.
Input

The first line of input contains an integer $$$T$$$ $$$(1 \le T \le 10^5)$$$, the number of test cases. Each of the next $$$T$$$ lines contains a single integer $$$N$$$ $$$(1 \le N \le 10^5)$$$.

Output

For each test case, output a single integer, the sum of the beauty of all positive integers less than or equal to $$$N$$$.

Example
Input
1
5
Output
8
Note

For $$$N=5$$$, we need to find the sum of beauty for all integers $$$K$$$, such that $$$1 \le K \le N$$$. Let's start by finding the beauty of each number $$$K$$$.

  • For $$$K=1$$$: $$$1$$$ and $$$5$$$ are co-prime, we have $$$GCD(1-1,5) = GCD(0,5) = 5$$$. So the beauty of $$$K=1$$$ is $$$5$$$.
  • For $$$K=2$$$: $$$2$$$ and $$$5$$$ are co-prime, we have $$$GCD(2-1,5) = GCD(1,5) = 1$$$. So the beauty of $$$K=2$$$ is $$$1$$$.
  • For $$$K=3$$$: $$$3$$$ and $$$5$$$ are co-prime, we have $$$GCD(3-1,5) = GCD(2,5) = 1$$$. So the beauty of $$$K=3$$$ is $$$1$$$.
  • For $$$K=4$$$: $$$4$$$ and $$$5$$$ are co-prime, we have $$$GCD(4-1,5) = GCD(3,5) = 1$$$. So the beauty of $$$K=4$$$ is $$$1$$$.
  • For $$$K=5$$$: $$$5$$$ and $$$5$$$ are not co-prime, so the beauty of $$$k=5$$$ is $$$0$$$.

Thus, the sum of beauty for all integers $$$K$$$, such that $$$1 \le K \le 5$$$ is $$$5 + 1 + 1 + 1 + 0 = 8$$$. Therefore, the answer for $$$N=5$$$ is $$$8$$$.