### 问题描述 小蓝很喜欢素数，于是他准备了这样一个问题来考考你： 给出一个长度为 $n$ 的正整数序列 $a$，对于每个 $a_i$，请你求出 $a_1,a_2,\dots,a_{i-1}$ 中，与 $a_i$ 互质的数有多少个。两个数字互质当且仅当他们的最大公因数为 $1$。为了让问题简单一些，小蓝保证每个 $a_i$ 的所有**质因数**都小于 $20$。 ### 输入格式 第一行一个整数 $n \space (1 \leq n \leq 10^4)$，代表序列的长度。 接下来一行 $n$ 个整数 $a_i \space (1 \leq a_i \leq 10^6)$，代表序列中每个元素的值。保证每个 $a_i$ 的所有**质因数**都小于 $20$。 ### 输出格式 输出一行 $n$ 个整数，第 $i$ 个整数代表在 $a_i$ 之前与 $a_i$ 互质的数的个数。 ### 样例输入 ``` 6 1 1 4 5 1 4 ``` ### 样例输出 ``` 0 1 2 3 4 4 ```