From the Problem Setter

Problem G (!Andd) is a harder version of this problem.

Problem Statement

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

• Change $X$ to either $X+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 input values are integers.
• $1 \le N \le 2 \times 10^4$
• $0 \le A_i < 2^{10}$

Output

Print $N$ lines.

On the $i(1 \le i \le N)$-th line, print 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

2
3

4
30 29 16 26

2
4
5
9

10
26 7 10 0 10 30 21 30 31 20

2
4
6
6
9
17
22
34
60
63