题面

今天是先先的生日，为了庆祝自己的生日，先先邀你来玩一个游戏。

先先让 $N$ ($1\leq N\leq 10^5$) 个朋友坐成一个圈。除了 $1$ 号与 $N$ 号朋友外，$i$ 号朋友与 $i-1$ 号和 $i+1$ 号朋友相邻。$N$ 号朋友与 $1$ 号朋友相邻。先先用很多纸条装满了一个桶，每一张包含了一个不一定是独一无二的 $1$ 到 $10^6$ 的数字。

接着每一个朋友 $i$ 从桶中取出一张纸条 $A_i$。每个朋友轮流走上一圈，同时拍打所有手上数字能整除在自己纸条上的数字的朋友的头，然后坐回到原来的位置。朋友们希望先先帮助他们确定，每一个朋友需要拍打的朋友的头数量。

输入格式

第一行包含一个整数$n$. 接下来包含$n$个整数$a_i$。

输出格式

第一到第 𝑁 行，第 𝑖 行的输出表示第 𝑖 个朋友要拍打的头的数量。

样例 #1

样例输入 #1

5 
2 
1 
2 
3 
4

样例输出 #1

2 
0 
2 
1 
3

提示

对于$20$%的数据，$1 \leq n \leq 100$ 对于其他数据， $1 \leq n \leq 10^5$