From the Problem Setter

This problem is a harder version of Problem F (Andd).

Problem Statement

There are a sequence $A$ of non-negative integers of length $N$ and a variable $X=1$. For $i=1,2,\dots,N$, in this order, Vil-kun will perform the following operation.

• Change $X$ to $X \times A_i$ or $X\ \mathrm{AND}\ A_i$.

Here, $\mathrm{AND}$ denotes the bitwise AND.

For each $i(1 \le i \le N)$, find the number of distinct values that $X$ can take after the $i$-th operation.

Input

$N$
$A_1\ A_2\ \dots\ A_N$

• All inputs are integers.
• $1 \le N \le 2 \times 10^4$
• $0 \le A_i < 2^{10}$

Output

Output $N$ lines.

On the $i(1 \le i \le N)$-th line, output the number of distinct values that $X$ can take after the $i$-th operation, followed by a newline.

It can be proved that all answers are less than $2^{31}$ under the given constraints.

Sample

2
1 4

1
2

4
30 29 16 26

2
3
4
5

10
26 7 10 0 10 30 21 30 31 20

2
3
4
1
1
1
1
1
1
1