Given a sequence of integers $A$ consisting of n elements. For each integer $i$ from $1$ to $n$, count how many pairs of integers in sequence A have the greatest common divisor (GCD) equal to $i$.
### Input
- The first line contains an integer $n$.
- The second line contains n integers $A_i$.
### Output
- Output $n$ integers, where the $i^{th}$ integer is the number of pairs of integers with the smallest GCD equal to $i$.
### Constraints
- $1 \le n \le 10^6$.
- $1 \le A_i \le n$
### Example
Input:
```
8
5 1 5 6 8 8 3 5
```
Output:
```
21 2 1 0 3 0 0 1
```
