作問者より

この問題はF問題(Andd)を強化したものです。

問題文

長さ $N$ の非負整数列 $A$ と変数 $X=1$ があります。Vil君はこれから $i=1,2,\dots,N$ についてこの順に以下の操作を行います。

• $X$ を $X \times A_i$ または $X\ \mathrm{AND}\ A_i$ に変化させる

ここで、$\mathrm{AND}$ はビットごとの論理積を表します。

各 $i(1 \le i \le N)$ について $i$ 回目の操作後の $X$ としてあり得る値が何種類あるか求めてください。

入力

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

• 入力はすべて整数
• $1 \le N \le 2 \times 10^4$
• $0 \le A_i < 2^{10}$

出力

$N$ 行出力してください。

$i(1 \le i \le N)$ 行目には $i$ 回目の操作後の $X$ としてあり得る値の種類数を出力し、最後に改行してください。

なお、制約の条件下で答えは全て $2^{31}$ 未満になることが証明できます。

サンプル

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