Description

Original source: USACO 2008 Dec. Silver

Today is Bessie's birthday, and it's time for party games. Bessie has arranged for $N$ cows numbered $1\sim N$ to sit in a circle (so except for the last cow, the $i$-th cow is adjacent to the $(i-1)$-th and $(i+1)$-th cows, and the $N$-th cow is adjacent to the $(N-1)$-th and the $1$-st cow). Meanwhile, Farmer John brings a bucket containing a billion small slips of paper, each with an integer between $[1,10^6]$ written on it.

Next, each cow takes turns drawing a number $A_i\ (1\le A_i\le 10^6)$ from the massive bucket (these numbers do not need to be distinct). Then, the $i$-th cow walks around the circle, and if the number in cow $i$'s hand is divisible by the number in cow $j$'s hand $(j\neq i)$, cow $i$ will pat cow $j$ on the head. After completing the circle, cow $i$ returns to its original position.

The cows want you to help them calculate, for each cow, how many cows it needs to pat on the head?

Input Format

The first line contains an integer $N$;
The next $N$ lines each contain an integer $A_i$.

Output Format

Output $N$ lines, where the $i$-th line indicates the number of cows the $i$-th cow needs to pat.

Sample 1

The first cow will pat the second and third cows, the second cow will pat no cows, and so on.

5
2
1
2
3
4

2
0
2
1
3

Data Range and Hints

For all data, $1\le N\le 10^5$.