Description

It's Chrismas and time for party games! Fido has instructed his N (1 <= N <= 100,000) friends conveniently numbered 1..N to sit in a circle (so that friend i [except at the ends] sits next to friend i-1 and i+1; friend N sits next to friend 1). Each friend i then draws a number A_i (1 <= A_i <= 1,000,000) (which is not necessarily unique, of course). Taking turns, each friend i then takes a walk around the circle and pats the heads of all other friend j such that her number A_i is exactly divisible by friend j's number A_j; she then sits again back in her original position. The friends would like you to help them determine, for each friend, the number of other friends she should pat.

Input

The input consists of several test cases.For each case,there are N+1 lines. Line 1: A single integer: N; Lines 2..N+1: Line i+1 contains a single integer: A_i.

Output

Lines 1..N: On line i, print a single integer that is the number of other friends patted by friend i.

Sample

Input

5
2
1
2
3
4

Output

2
0
2
1
3

Source: fengyel