Description

今天是 Bessie 的生日，并且现在是聚会的游戏时间。Bessie 让编号为1~N的 N头奶牛围成一个圈坐（所以除了最后一头牛，第 i头奶牛与第i-1 和i+1 头奶牛相邻，第N头奶牛和第N-1头与第1头奶牛相邻）。同时，Farmer John 拿了个桶，在桶里装了十亿张小纸条，每张小纸条上写有某个范围在[1,10^6]的整数。

接着，每头奶牛轮流从这个巨桶中抽取一个数Ai(1=<Ai<=10^6)（当然这些数没必要两两不同）。然后第i头奶牛走一圈，如果奶牛i手中的数字能够被奶牛j(i!=j)手中的数字整除，那么奶牛i会拍奶牛j的头。走完一圈后，奶牛i回到原来的位置。

奶牛们想让你帮他们计算，对于每头奶牛，它需要拍多少头奶牛的头？

Input Format

第一行包含一个整数N； 接下来第二到第N+1 行每行包含一个整数Ai 。

Output Format

一到第N行，第i行的输出表示第i头奶牛要拍打的牛数量。

Sample

输入

5
2
1
2
3
4

输出

2
0
2
1
3

第一头奶牛会拍第二、第三头奶牛，第二头牛不会拍任何奶牛的头，等等

Hint

对于全部数据1=<N<=10^5