In this question, you will be asked to implement 4 operations on two large natural numbers. The operations are as follows:

1) Add(a, b) : Compute a + b

2) Subtract(a, b) : Compute a - b. You are given that a > b

3) Multiply(a, b) : Compute a * b

4) Divide(a, b) : Compute a / b. 

Input

The first line contains t: the number of test cases.

t test cases follow

Each test case contains 3 lines:

The first line contains two space separated integers n₁ and n₂ denoting the number of digits in the two numbers.

The second line contains the two space separated sequences a and b of n₁ and n₂ digits respectively. 

The third line contains the opcode. If the opcode is 1, then the output should be the result of Add(a, b), if 2 then Subtract(a, b), if 3 then Multiply(a, b) and if 4 then Divide(a, b).

Output

For each test case, print the corresponding output on a new line

Constraints

1 <= t <= 10
10 <= n₁, n₂ <= 1000

Example

Input:
4
9 9
845236792 426347821
1
9 9
845236792 426347821
2
9 9
845236792 426347821
3
9 9
845236792 426347821
4

Output:
1271584613
418888971
360364864498230232
1