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
Output format
The output must consist of a single line containing Q space-separated integers. The ith integer denotes the answer to the ith task.
Constraints
1≤Q≤103
1≤N≤106