Keystroke

Time limit1sMemory limit1024 MB

Summary

Count how many subsets of the four keys can produce the given set of received row numbers and set of received column numbers.

Level: Easy3 of 10
Topics: Brute force, Combinatorics, Implementation, Bit manipulation
Solved: No attempts yet

Problem

You are designing a numeric keypad for the numbers 1 to 4, where each number is associated with a unique key. All of the keys are arranged as a 2 × 2 matrix, and there is a detection circuit beneath the keypad. When a key is pressed, the circuit transmits the keystroke signals to the controller, which receives the row number and column number. We can use a pair (row, column) to represent a keystroke event. Precisely speaking, when you press the key of number 𝑖 where 𝑖 ∈ {1, 2, 3, 4}, the controller receives the pair (⌊(i − 1)/2⌋,(i − 1) mod 2). For example, when you press key 3, the controller gets (1, 0) as the keystroke signal. You would like to press several keys at the same time for some reason. When you do this, the controller can still receive their corresponding row and column numbers. However, their row numbers are mixed together, as are the column numbers. For example, when you press keys 1 and 4 simultaneously, the controller gets row numbers {0, 1} and column numbers {0, 1}, because key 1 emits (0, 0) and key 4 emits (1, 1). Another example is that when you press keys 1 and 2 simultaneously, the controller can only receive ({0}, {0, 1}) because key 1 emits (0, 0), key 2 emits (0, 1), and their row numbers are the same. Notice that different keystroke combinations may lead to the same signal. Pressing keys 2 and 3 gets ({0, 1}, {0, 1}), which is identical to pressing 1 and 4. Pressing keys 1, 2, 3, 4 simultaneously gets the same result. Given a keystroke signal in the (row, column)-paired form, write a program to identify the total number of possible keystroke combinations that can lead to this signal.

Input

The first line of the input is a positive integer that specifies the number of test cases. Each test case follows immediately in the next line after the previous one. In each test case, its first line gives you two positive integers m and n. Its second line gives you m distinct integers that are the received row numbers. Its third line gives you n distinct integers that are the received column numbers. All numbers in the same line are space-delimited.

Output

Output the result in a single line for each test case.

Constraints

There are at most 10 test cases.
1 ≤ m, n ≤ 2.

Examples2

Example 1
Input
```
2
2 1
0 1
0
1 2
1
0 1
```
Expected output
```
1
1
```
Example 2
Input
```
2
2 2
0 1
0 1
1 1
1
1
```
Expected output
```
7
1
```