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

题目描述

恰逢 H 国国庆，国王邀请 $n$ 位大臣来玩一个有奖游戏。

首先，他让每位大臣在各自的手心里写下一个正整数。

然后，任意两位大臣互相向对方展示自己手心里的数字。如果对方大臣手心里的数字能够整除自己手心里的数字，那么自己就可以获得国王奖赏的一个金币。

当任意两位大臣都向对方展示过自己手心里的数字后，游戏结束。

国王想知道最后每位大臣会获得多少个金币。

自然地，这个任务交给了你。

请你按顺序依次输出 1 ~ n 号大臣最后获得的金币个数。

输入格式

第一行包含一个整数 $n$，表示大臣的人数

接下来 $n$ 行：每行一个整数 Ai，依次表示 1 ~ n 号大臣写在自己手心里的数字

输出格式

$n$ 行：每行一个整数，依次表示 1 ~ n 号大臣最后获得的金币个数

样例输入

5 
2 
1 
2 
3 
4

样例输出

2 
0 
2 
1 
3

数据范围

约 40% 的数据：1 <= n <= 5,000

100%的数据：1 <= n <= 100,000， 1 <= Ai <= 1,000,000