panda-and-gcd

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

SAMPLE INPUT
4
3 2 2 3

SAMPLE OUTPUT
3 3 3 3

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]}.

Source: hackerearth | Difficulty: UNKNOWN_DIFFICULTY


Solutions: