Problem Description

You have a permutation $a$ of length $n$. The value of an interval $[l, r]$ is defined as follow:

$$v(l, r) = \max_{l \leq i < j \leq r}{\gcd(a_i, a_j)}$$

In mathematics, the greatest common divisor($\gcd$) of two or more integers, which are not all zeroes, is the largest positive integer that divides each of the integers. For two integers $x, y$, the greatest common divisor of $x$ and $y$ is denoted by $\gcd(x, y)$. For example, the $\gcd$ of $8$ and $12$ is $4$, that is, $\gcd(8, 12) = 4$.

You need to calculate for each $x(1 \leq x \leq n)$, how many pairs of $l, r(1 \leq l < r \leq n)$ satisfy that $v(l, r) = x$.

Input

This problem contains multiple test cases.

The first line contains an integer $T$ indicating the number of test cases.

For each test case, the first line contains one integer $n$ ($2 \leq n \leq 10 ^ 5$).

The second line contains $n$ integers $a_i$ ($1 \leq a_i \leq n$). It's guaranteed that $a$ is a permutation.

It's guaranteed that $\sum{n} \leq 10 ^ 6$.

Output

For each test case, output $n$ lines.

The i-th line contains an integer indicating the answer for $x = i$.

1
5
1 4 3 5 2

8
2
0
0
0