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}\)