Cow Pat Counting Game

Bessie is hosting a birthday party and the cows are playing a fun game! The cows numbered from 1 to N are sitting in a circle. Each cow draws an integer A_i from a barrel where 1 ≤ A_i ≤ 1,000,000 and 1 ≤ N ≤ 100,000.

Then, each cow i walks around the circle and pats the head of every other cow j such that A_i is exactly divisible by A_j. In other words, cow i pats cow j if and only if:

\(A_i \mod A_j = 0\)

Your task is to determine, for each cow, the number of other cows it should pat.

inputFormat

The input begins with a single integer N on a line by itself. The next line contains N integers representing A₁, A₂, ..., A_N, separated by spaces.

\(1 \leq N \leq 100\,000\) and \(1 \leq A_i \leq 1\,000\,000\).

outputFormat

Output N lines. The i-th line should contain a single integer, the number of cows that cow i should pat. Note that a cow never pats itself.

sample

3
3 1 2

1
0
1