题目描述

今天是贝茜的生日，奶牛们要玩一个聚会游戏。贝茜让 $N$ 头奶牛围成一个圆圈坐好，编号为 $1\sim N$。除了首尾相接的位置，奶牛 $i$ 的两边分别是奶牛 $i-1$ 和 $i+1$，奶牛 $N$ 和奶牛 $1$ 也相邻。

农夫约翰准备了一个桶，里面装着十亿张纸条，每张纸条上写着一个整数。每头奶牛 $i$ 从桶中抽出一个数 $A_i$。不同奶牛抽到的数可以相同。

然后奶牛们轮流起身绕着圆圈走一圈。奶牛 $i$ 会拍拍所有满足下面条件的其他奶牛 $j$ 的头：$A_i$ 能被 $A_j$ 整除，即 $A_i\bmod A_j=0$。之后它再回到自己的座位。

请分别求出每头奶牛需要拍多少头其他奶牛的头。奶牛不会拍自己的头。

输入格式

第一行一个整数 $N$。

接下来 $N$ 行，第 $i$ 行一个整数 $A_i$。

输出格式

输出 $N$ 行，第 $i$ 行表示奶牛 $i$ 需要拍头的其他奶牛数量。

样例输入 1

5 
2 
1 
2 
3 
4

样例输出 1

2 
0 
2 
1 
3

样例输入 2

1
175566

样例输出 2

0

样例输入 3

2
513646
800365

样例输出 3

0
0

说明/提示

样例 1 中，$5$ 头奶牛抽到的数依次为 $2,1,2,3,4$。

第 $1$ 头奶牛会拍第 $2$ 头和第 $3$ 头奶牛的头；第 $2$ 头奶牛不会拍任何奶牛的头。其他奶牛同理。

数据范围

$1\le N\le 10^5$。

$1\le A_i\le 10^6$。