Two factors

4

1 votes
Combinatorics, Inclusion-Exclusion, Math, Medium
Problem

You are given a single integer N. You are required to determine the sum of all the integers X where 1X 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 ith integer denotes the answer to the ith task.

Constraints

1Q103

1N106

Time Limit: 1
Memory Limit: 256
Source Limit:
Explanation
  1. 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.
  2. For N=24, the integers satisfying the constraints are 6, 12, and 18, hence the sum is 36.
Editor Image

?