Patting Heads

It's Bessie's birthday, and it's time for party games! Bessie has arranged the $N$ cows ($1 \le N \le 100000$), conveniently numbered $1 \dots N$, in a circle, so that cow $i$ sits between cows $i-1$ and $i+1$, and cow $N$ sits next to cow $1$.

Farmer John fills a barrel with a huge number of paper slips, each holding an integer between $1$ and $1000000$. Each cow $i$ then draws one integer $A_i$ ($1 \le A_i \le 1000000$) from the barrel; the values are not necessarily distinct.

Taking turns, each cow $i$ walks around the circle and pats the head of every other cow $j$ whose number $A_j$ exactly divides her own number $A_i$, then returns to her seat.

For each cow, determine how many other cows she pats.

• Line $1$: a single integer $N$.
• Lines $2 \dots N+1$: line $i+1$ contains the integer $A_i$.

• Print $N$ lines. On line $i$, print a single integer: the number of other cows that cow $i$ pats.

In the example, the first cow (number $2$) pats the second cow (number $1$, since $2$ is divisible by $1$) and the third cow (number $2$), for a total of $2$. The second cow (number $1$) pats no one, because no other cow drew a number that divides $1$.