C. Bit And Segment
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

Given an array of integers $$$a$$$ of length $$$n$$$. Let's say that segment $$$[l,r]$$$ is $$$i$$$-$$$th \: good$$$ if:

  • $$$1 \leq l \leq i \leq r \leq n$$$;
  • $$$ a_{l}\, \& \, a_{l+1} \, \& \, ... \, a_{i} \, \& \, ... \, a_{r-1} \, \& \,a_{r}\, =\, a_{i}$$$.

For each $$$i$$$ from $$$1$$$ to $$$n$$$, count all segments which are $$$i$$$-$$$th \: good$$$.

Here $$$\&$$$ denotes the bitwise AND operation.

Input

Each test consists of multiple test cases. The first line contains a single integer $$$t$$$ $$$(1 \le t \le 10^4)$$$ — the number of test cases. The description of the test cases follows.

The first line of each test case contains a single integer $$$n$$$ $$$(1 \le n \le 10^5)$$$ — the length of the array $$$a$$$.

The second line of each test case contains $$$n$$$ integers $$$a_1, a_2, \ldots, a_n$$$ $$$(1 \le a_i \le 10^6)$$$ — the elements of the array $$$a$$$.

It is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$10^5$$$.

Output

For each test case, output $$$n$$$ integers on a single line — the number of $$$i$$$-$$$th \: good$$$ segments for each $$$i$$$ $$$(1 \le i \le n)$$$.

Example
Input
2
5
3 7 6 2 10
5
4 1 3 1 4
Output
2 1 2 8 1
1 3 1 3 1
Note

For the first test case, $$$a=[3,7,6,2,10]$$$.

  • The $$$1$$$-$$$th \: good$$$ segments are : $$$[1,1], [1,2]$$$.
  • The $$$2$$$-$$$th \: good$$$ segments are : $$$[2,2]$$$.
  • The $$$3$$$-$$$th \: good$$$ segments are : $$$[2,3],[3,3]$$$.
  • The $$$4$$$-$$$th \: good$$$ segments are : $$$[1,4],[2,4],[3,4],[4,4],[1,5],[2,5],[3,5],[4,5]$$$.
  • The $$$5$$$-$$$th \: good$$$ segments are : $$$[5,5]$$$.