[Usaco2008 Dec]Patting Heads 轻拍牛头

今天是贝茜的生日。为了庆祝，她邀请你玩一个游戏。

贝茜让 $N$ 头奶牛围成一圈。除编号为 $1$ 和 $N$ 的奶牛外，编号为 $i$ 的奶牛与编号为 $i-1$ 和 $i+1$ 的奶牛相邻；编号为 $N$ 的奶牛与编号为 $1$ 的奶牛相邻。

农夫约翰准备了许多纸条，每张纸条上写有一个 $1$ 到 $10^6$ 之间的整数，不同纸条上的整数可以相同。每头奶牛 $i$ 各取出一张纸条，其上的整数记为 $A_i$。

每头奶牛依次绕牛圈走一周，并拍打所有满足纸条上的整数能够整除 $A_i$ 的其他奶牛的头，然后回到原来的位置。请你计算每头奶牛需要拍打多少头奶牛。

输入格式

第一行包含一个整数 $N$。

接下来 $N$ 行，第 $i$ 行包含一个整数 $A_i$，表示第 $i$ 头奶牛纸条上的整数。

输出格式

输出 $N$ 行，第 $i$ 行包含一个整数，表示第 $i$ 头奶牛需要拍打的奶牛数量。

样例输入

5
2
1
2
3
4

样例输出

2
0
2
1
3

样例解释

第 $1$ 头奶牛会拍打第 $2$ 头和第 $3$ 头奶牛；第 $2$ 头奶牛不会拍打任何奶牛，其余情况同理。

数据范围

• $1\le N\le 10^5$；
• $1\le A_i\le 10^6$。

来源与许可

本题为 USACO 2008 December 试题「Patting Heads」，题面与测试数据整理自 BZOJ。

样例 1

输入

5
2
1
2
3
4

输出

2
0
2
1
3