You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

题目描述

原题来自：USACO 2008 Dec. Silver

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

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

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

输入格式

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

输出格式

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

样例

5
2
1
2
3
4

2
0
2
1
3

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

数据范围与提示

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