D. Bacteria Culture
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

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$$$.

Example
Input
2
5 10
1 3 0 6 2
4 10 0 10 8
3 12
3 4 0
12 10 0
Output
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$$$.