Kaho's Xor Query

初めに,つの自然数が与えられています.

カホさんは自然数のペアに対し以下を満たす整数のみから構成される長さの数列の個数に興味があります.

・

・

彼女は上記のタイプのクエリに回答えようとしましたが,XORを習ったばかりの彼女には難しいようで

代わりにXORのエキスパートであるあなたに助けを求めてきました.

彼女の代わりに上記のクエリに回答えてください.なお結果はで出力してください.

(注記 : は排他的論理和(Exclusive OR = XOR)を指す)

・入力はいずれも整数である

・

・

・

▷各クエリにおいて以下が成り立つ.

・

入力は以下の形式で与えられます.

N K Q
Query_1
Query_2
.
.
.
Query_Q

すべてで行出力してください.

行目には番目のクエリに対する数列の個数をで出力してください.

最後に改行してください.

2 3 4
2 3
0 6
3 3
6 7

16
56
8
16

5 5 1
17 30

14680064

1000000 60 2
695360817523154042 708792922384807709
334945677305323519 510742335751990503

568318416
47700334

結果はで出力してください.