Background

过耶鼠圣诞日了, 众多土拨鼠围成一个圈玩游戏

Description

$n$只土拨鼠首尾相连围成一个圈, 编号从$1$到$n$.

每只土拨鼠都有一个幸运数字$a_i$, 从$1$号开始, 每只土拨鼠都会绕圈一周. 假如现在是第$x$只土拨鼠正在绕圈, 他发现第$y$只土拨鼠的幸运数字$a_y$能够整除$a_x$, 则他会给第$y$只土拨鼠一个小红花, 现在我们想知道, 每一只土拨鼠都给出了几只小红花?

Format

Input

第一行一个数字$n$, 表示土拨鼠数量

接下来$n$行, 每行一个数字$a_i$, 表示第$i$只土拨鼠的幸运数字.

Output

输出$n$行, 表示每只土拨鼠给出的小红花数量.

Samples

5
2
1
2
3
4

2
0
2
1
3

样例解释

第1只土拨鼠将会给第2, 3只土拨鼠小红花

第2只土拨鼠不会给任何一只土拨鼠小红花

第4只土拨鼠会给第2只土拨鼠小红花

第5只土拨鼠会给第1, 2, 3只土拨鼠小红花

Limitation

$1 <= n <= 10^5, 1<=a_i<=10^6$