Panda and gcd
Problem
One day while playing with GCD (Greatest Common Divisor), Panda got struck in a problem, so help Panda to solve his problem. His problem follows as - Panda have N integers, for each integer count the number of subsets with gcd i%1000000007, where i denotes the ith integer which panda have.
INPUT:
Input consists of two lines.
The first line contains the integer N.
Next line contains N integers.
OUTPUT:
N space separated integers, where each integer represents the number of subsets with gcd i%1000000007, where i denotes the ith integer which panda have.
CONSTRAINTS:
1 ≤ N ≤ 10^6
1 ≤ Ai ≤ N
Time Limit: 1
Memory Limit: 256
Source Limit:
Explanation
The number of subsets with the gcd of 2 is 3. They are {[2],[2],[2,2]}.
The number of subsets with the gcd of 3 is 3. It is {[3],[3],[3,3]}.
