作問者より

この問題は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