Two factors
69% Success4172 Attempts30 Points1s Time Limit256MB Memory1024 KB Max Code
You are given a single integer \(N\). You are required to determine the sum of all the integers \(X\) where \(1≤X\) and \(GCD(X,N)\) contain at least \(2\) distinct prime factors.
Here, \(GCD(X,N)\) denotes the greatest common divisor of \(X\) and \(N\).
Note: Refer to the sample explanation section for more details.
Input format
- First line of each test case: A single integer \(Q\) denoting the number of tasks
- Each Q lines: A single integer \(N\) as described in the problem statement
Output format
The output must consist of a single line containing \(Q\) space-separated integers. The \(i_{th}\) integer denotes the answer to the \(i_{th}\) task.
Constraints
\(1 ≤ Q ≤ 10^{3}\)
\(1 ≤ N ≤ 10^{6}\)
Examples
Input
2 12 24
Output
6 36
Explanation
- For \(N=12\), there is only a single integer \(6\) in the range \(1\) to \(11\) whose \(GCD\) with \(12\) has at least \(2\) prime factors. Hence, the answer is \(6\).
- For \(N=24\), the integers satisfying the constraints are \(6\), \(12\), and \(18\), hence the sum is \(36\).
Please login to use the editor
You need to be logged in to access the code editor
Loading...
Please wait while we load the editor
Loading Editor...
Results