マルチテストについての説明はこちら (サンプル問題を確認されていない方のみお読みください。)
配点:300 点
問題文
N 個の相異なる整数 A1,A2,…,AN と,各頂点に 1 から N までの番号が付けられた N 頂点の有向グラフ G があります.
ここで,1≤i,j≤N なる任意の相異なる 2 整数 i,j について Ai&Aj=Ai であるとき,またそのときに限り,G において 頂点 i から 頂点 j へ向かう有向辺が存在します.
- なお,2 非負整数 a,b に対して a&b は a,b の bitwise AND を表す.
G の頂点であって出次数が 0 であるものの個数を求めてください.
制約
- Φ=1
- 1≤N≤4×105
- 0≤Ai<220(1≤i≤N)
- Ai=Aj(1≤i<j≤N)
- 入力はすべて整数
入力
各テストケースの入力は,それぞれ以下の形式で与えられる:
出力
答えを出力せよ.
サンプル
G は次のようなグラフになります:
![](https://mermaid.ink/img/pako:eNplkDtPwzAQgP-KdXMa-RknHpg6lgU24g5WbWgEiSPjSJQo_50jqRQk7MX3nfXdY4ZL9AEMvCU3XsnTyQ4ED2stMNKys4XzRjgSTtpmJwKJIK3YiUQiSct3opAo9MgN3eXkcHgg_G8g7oL_gYIC-pB613nscv5NWcjX0AcLBp_epXcLdljwn5tyfL4NFzA5TaGAafQuh2PncLgezKv7-EQ6ugHMDF9guGrKWnKhJGVNrbUq4AaGSVVSpqloBGeVklotBXzHiAZaVhIvFzWt64pq3ay6lzW51Qy-yzE9bktdd7v8AN6QX9Q?type=png)