You are given 'n' integers k₁, k₂ ... k_n and an integer 'x', which satisfy the equation x₁^k₁ * x₂^k₂ * ... * x_n^k_n = x. You are also given values a₁, a₂ ... a_n and y₁, y₂ ... y_n. Your task is to find the least positive value 'v', that can be taken by the expression: a₁*x₁^y₁ + a₂*x₂^y₂ + ... + a_n*x_n^y_n. Note that x₁, x₂, x₃ ... x_n are some variables (not necessarily integers), which can only take positive values.

Input

The first line of input contains a single integer 't', denoting the number of test cases.
The first line of each testcase contains two space separated integers 'n' and 'x'.
Next line contains 'n' integers k₁, k₂ ... k_n.
Next line contains 'n' integers a₁, a₂ ... a_n.
Next line contains 'n' integers y₁, y₂ ... y_n.

Output

For each testcase output the least positive value 'v' that can be taken by the expression. To avoid floating point errors, round it off to the nearest integer.

For example, 12.6 is rounded off to 13, and 12.4 is rounded off to 12. To avoid ambiguity, there will be no test case for which the fractional part of the answer equals 0.5.

Example

Input:
2
1 4
2
3
3
2 6
1 1
1 1
1 1

Output:
24
5

Constraints

t <= 25
1 <= n <= 20
1 <= x <= 1000000
1 <= k_i, a_i, y_i <= 20
x_i > 0

Explanation

Test case 1: x₁² = 4. Therefore, x₁ = 2 and 3*x₁³ = 24.
Test case 2: x₁*x₂ = 6. Minimum value of x₁ + x₂ is 2*sqrt(6) = 4.89897. x₁ = sqrt(6) and x₂ = sqrt(6) gives this solution. Answer is 4.89897, which when rounded off to the nearest integer equals 5.