题目描述

原题来自：USACO 2008 Dec. Silver

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

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

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

输入格式

第一行包含一个整数$\red N$； 接下来第二到第$\red{ N+1 }$行每行包含一个整数$\red{ A_i}$。

输出格式

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

样例

输入样例

5
2
1
2
3
4

输出样例

2
0
2
1
3

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

数据范围与提示

对于全部数据，$\red{1\le N\le 10^5}$。