問題 G - snowy bunny

Time Limit: 2 seconds / Memory Limit: 256 MB

問題

ゆきうさぎは二進法での計算が好きである．今日は，「ゆきうさぎ変換」という非負整数の変換を考えている．

「ゆきうさぎ変換」は，2^M 未満の非負整数を受け取り，2^N 未満の非負整数を返す．「ゆきうさぎ変換」は，2⁰ の位，2¹ の位，…，2^M-1 の位の M 個について，その「ゆきさき」を決めることで定まる．各「ゆきさき」は，2⁰ の位，2¹ の位，…，2^N-1 の位の N 個のうちのいくつか (0 個でもすべてでもよい) である．ここで，M 個の「ゆきさき」を合わせると，N 個の位をちょうど 1 回ずつ選んでいなければならない．次の図は M = 5，N = 6 のときの「ゆきうさぎ変換」の例を表している．

「ゆきさき」を定めると，「ゆきうさぎ変換」がどんな数を返すかは自然に決まる．M 個の位の 0 または 1 を，それぞれ「ゆきさき」のところにそのまま書き込んだものが，返される値である．次の図は，上の図の「ゆきうさぎ変換」で 19 (二進法で 10011) が 60 (二進法で 111100) になる様子を示している．

ゆきうさぎには，「かっこいい」と思っている数や，「かわいい」と思っている数がそれぞれいくつかある．これらは以下の特徴を持っている．

• p, q を「かっこいい」と思っているとき，AND(p, q), OR(p, q) も「かっこいい」と思っている．
• p, q を「かわいい」と思っているとき，AND(p, q), OR(p, q) も「かわいい」と思っている．

ここで，AND や OR はビット演算の AND や OR である．すなわち，二進法の各桁ごとに論理積や論理和を計算した値を表す．以下に例を示す．

• AND(12, 5) = 4 (二進法で書けば AND(1100, 0101) = 0100 である)．
• OR(12, 5) = 13 (二進法で書けば OR(1100, 0101) = 1101 である)．

ゆきうさぎは，「かっこいい」と思っている数を受け取ったとき必ず「かわいい」と思っている数を返すような「ゆきうさぎ変換」が大好きである．そのような「ゆきうさぎ変換」が何通りあるかをぜひ知りたい．

入力

入力の 1 行目はテストケースの個数を表す整数 T を含む．以下 T 個のテストケースが続く．

M N A B
X1 ... XA
Y1 ... YB

各テストケースの 1 行目は 4 つの整数 M, N, A, B を含む．

各テストケースの 2 行目は A 個の整数 X₁, …, X_A を含む．これらはゆきうさぎが「かっこいい」と思っている数を表す．

各テストケースの 3 行目は B 個の整数 Y₁, …, Y_B を含む．これらはゆきうさぎが「かわいい」と思っている数を表す．

出力

各テストケースごとに，ゆきうさぎが「かっこいい」と思っている数を受け取ったとき必ず「かわいい」と思っている数を返すような「ゆきうさぎ変換」の個数を 1 行に出力せよ．

制約

• 2 ≤ T ≤ 10．
• 1 ≤ M ≤ 10．
• 1 ≤ N ≤ 6．
• 1 ≤ A ≤ 2^M．
• 1 ≤ B ≤ 2^N．
• 0 ≤ X₁ < … < X_A ≤ 2^M - 1．
• 0 ≤ Y₁ < … < Y_B ≤ 2^N - 1．
• AND(X_i, X_j), OR(X_i, X_j) ∈ {X₁, …, X_A}．
• AND(Y_i, Y_j), OR(Y_i, Y_j) ∈ {Y₁, …, Y_B}．

部分点

100 点中 25 点分のデータは以下を満たす．

• 1 ≤ M ≤ 4．
• 1 ≤ N ≤ 4．

入出力例

入力例 1

3
3 2 4 3
2 3 6 7
0 1 3
3 4 8 16
0 1 2 3 4 5 6 7
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
4 4 8 4
0 1 2 3 8 9 10 11
0 2 4 6

出力例 1

5
81
16

1 つ目のテストケースにおいては，以下の 5 通りの「ゆきうさぎ変換」が条件を満たす．

2 つ目のテストケースにおいては，M = 3，N = 4 のときのすべての「ゆきうさぎ変換」が条件を満たす．

入力例 2

2
5 6 6 11
2 3 14 15 19 31
0 2 16 18 19 20 22 23 60 62 63
10 6 1 1
776
34

出力例 2

330
21609