该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

Description

奶牛拍头

今天是 Bessie 的生日, 并且现在是聚会的游戏时间。Bessie 让编号为 $1 \sim N$ 的 $N$ 头奶牛围成一个圈坐（所以除了最后一头牛, 第 $i$ 头奶牛与第 $i-1$ 和 $i+1$ 头奶牛相邻, 第 $N$ 头奶牛和第 $N-1$ 头与第 1 头奶牛相邻）。同时, Farmer John 拿了个桶, 在 桶里装了十亿张小纸条, 每张小纸条上写有某个范围在 $\left[1,10^6\right]$ 的整数。 接着, 每头奶牛轮流从这个巨桶中抽取一个数 $A_i\left(1 \leq A_i \leq 10^6\right)$ （当然这些数没必要两两不同）。然后第 $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 \leq N \leq 10^5$。

Source