Description

You are given two integer sequences $a_1, a_2, \ldots, a_n$ and $b_1, b_2, \ldots, b_n$, and an integer $M$.

In one operation, choose two integers $l$ and $r$ ($1 \le l \le r \le n$). For every $i$ ($l \le i \le r$), replace $a_i$ with $\min(2 \cdot a_i, M)$.

Find the minimum number of operations required to transform $a$ into $b$. If it is impossible, print $-1$.

Input

Each test file contains multiple test cases. The first line contains the number of test cases $T$ ($1 \le T \le 10^4$). The description of the test cases follows.

The first line of each test case contains two integers $n$ and $M$ ($1 \le n \le 2 \cdot 10^5$, $1 \le M \le 10^9$).

The second line contains $n$ integers $a_1, a_2, \ldots, a_n$ ($0 \le a_i \le M$), the initial sequence.

The third line contains $n$ integers $b_1, b_2, \ldots, b_n$ ($0 \le b_i \le M$), the target sequence.

It is guaranteed that the sum of $n$ over all test cases does not exceed $2 \cdot 10^5$.

Output

For each test case, print the minimum number of operations required to transform $a$ into $b$. If it is impossible, print a single integer $-1$.

Sample Input 1

2
5 10
1 3 0 6 2
4 10 0 10 8
3 12
3 4 0
12 10 0

Sample Output 1

2
-1

Note

In the first test case, apply the operation twice to the interval $[1, 5]$. After the first operation, the sequence becomes $[2, 6, 0, 10, 4]$, and after the second operation, it becomes $[4, 10, 0, 10, 8]$, so the answer is $2$.

In the second test case, the second element can only be $4$, $8$, or $12$ after any number of operations, so it can never become $10$.