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$.