## PATHEADS - Patting Heads

It's Bessie's birthday and time for party games! Bessie has instructed the N (1 ≤ N ≤ 100,000) cows conveniently numbered 1..N to sit in a circle (so that cow i [except at the ends] sits next to cows i-1 and i+1; cow N sits next to cow 1). Meanwhile, Farmer John fills a barrel with one billion slips of paper, each containing some integer in the range 1..1,000,000.

Each cow i then draws a number Ai (1 ≤ Ai ≤ 1,000,000) (which is not necessarily unique, of course) from the giant barrel. Taking turns, each cow i then takes a walk around the circle and pats the heads of all other cows j such that her number Ai is exactly divisible by cow j's number Aj; she then sits again back in her original position.

The cows would like you to help them determine, for each cow, the number of other cows she should pat.

### Input

• Line 1: A single integer: N.
• Lines 2..N+1: Line i+1 contains a single integer: Ai.

### Output

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

### Example

```Input:
5
2
1
2
3
4

Output:
2
0
2
1
3
```

The first cow pats the second and third cows; the second cows pats no cows; etc.

hide comments
 holmesherlock: 2017-04-03 19:33:17 easy one :-) vengatesh15: 2017-02-22 16:20:39 Finally removed from my todo-list Piyush Kumar: 2016-06-08 11:37:56 There is no need of sorting in this! anon: 2015-06-17 19:07:11 Sieve + STL =AC

 Added by: Neal Wu Date: 2008-12-26 Time limit: 0.780s Source limit: 50000B Memory limit: 1536MB Cluster: Cube (Intel G860) Languages: All except: ERL Resource: USACO Dec 2008