J. Bessie and Gifts
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

Bessie and Elsie are exchanging Christmas gifts. Elsie gifts Bessie an array $$$A$$$ of length $$$N$$$. However, Bessie forgot to get a gift for Elsie, so she came up with a devious plan: Bessie will create a gift for Elsie based on Elsie's gift!

A subarray $$$A_i, A_{i + 1}, \ldots, A_j$$$ of length $$$L = j-i+1$$$ is called special if none of the elements divides its length. Formally, it is special if for every $$$k$$$ with $$$i \le k \le j$$$ we have $$$$$$L \bmod A_k \ne 0.$$$$$$

Bessie's gift array $$$F$$$ is defined as follows: for each index $$$i$$$, the value $$$F[i]$$$ is the number of special subarrays in $$$A$$$ that start at index $$$i$$$.

Help Bessie compute the array $$$F$$$.

Input

The first line contains a single integer $$$T$$$ ($$$1 \leq T \leq 200000$$$) — the number of test cases.

Each test case begins with a line containing a single integer $$$N$$$ ($$$1 \leq N \leq 200000$$$) — the number of elements in the array $$$A$$$.

The second line of each test case contains $$$N$$$ integers $$$A_1, A_2, \ldots, A_n$$$ ($$$1 \leq A_i \leq N$$$).

The sum of $$$N$$$ over all test cases does not exceed $$$200000$$$.

Output

For each test case, print $$$N$$$ integers on a single line.

Example
Input
2
3
2 3 2
5
1 5 4 3 2
Output
1 1 1
0 2 2 1 1