G. Revolving Sushi
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

There are $$$n$$$ circular positions on the table in the sushi restaurant.

Initially, there are $$$x_i$$$ pieces of sushi in the plate at position $$$i$$$.Every second,the plate at position $$$i$$$ will be put into $$$a_i$$$ pieces of sushi.Then,the plates will revolve.

Formally:

  • The plate at position $$$1$$$ will move to position $$$2$$$;
  • The plate at position $$$2$$$ will move to position $$$3$$$;
  • ...
  • The plate at position $$$n$$$ will move to position $$$1$$$.

If for each position,the number of sushi is a multiple of $$$k$$$,customers will be happy.

Find the minimum waiting time to make customers happy.If no solution,output $$$-1$$$ instead.

Input

The first line of input will contain a single integer $$$t(t \leq 10^5)$$$, denoting the number of test cases.

Each test case contains three lines.

The first line contains two space-separated integers $$$n$$$,$$$k(1\leq n \leq 4*10^5,1\leq k \leq 10^9)$$$.

The next line contains $$$n$$$ integers:$$$x_1$$$,$$$x_2$$$,...$$$x_n(1 \leq x_i \leq 10^9)$$$.

The next line contains $$$n$$$ integers:$$$a_1$$$,$$$a_2$$$,...$$$a_n(1 \leq a_i \leq 10^9)$$$.

It's guaranteed that the sum of $$$n$$$ over all test cases will not exceed $$$4*10^5$$$.

Output

For each test case,output on a new line — the minimum waiting time to make customers happy.If no solution,output $$$-1$$$ instead.

Example
Input
5
3 2
1 2 3
1 2 2
4 4
1 1 1 1
1 1 1 1
4 8
1 3 5 7
2 4 6 8
4 3
3 6 9 12
1 1 1 1
4 6
1 6 1 2
6 7 7 6
Output
2
3
-1
0
10
Note

Test case $$$1$$$:

Note $$$p_i$$$ as the number of sushi in the plate currently in position $$$i$$$.

Initially:$$$p=[1,2,3]$$$;

The $$$1_{st}$$$ second:$$$p=[5,2,4]$$$;

The $$$2_{nd}$$$ second:$$$p=[6,6,4]$$$.

After $$$2$$$ seconds, all numbers are multiples of $$$k=2$$$, so the answer is $$$2$$$.