Ecrade was lost in thought while watching people wandering around and waiting in the cafeteria, and thus he came up with the following problem.

There are $n$ areas in the cafeteria. When the cafeteria is about to open, the $i$-th area has $a_i$ students waiting and $b_i$ empty seats. It is guaranteed that $\sum_{i=1}^n a_i \le \sum_{i=1}^n b_i$.

At each moment after the cafeteria opens, the following two events occur in sequence:

1. Students currently waiting in each area will sit in the empty seats of that area as much as possible. Specifically, suppose the $i$-th area currently has $x_i$ students waiting and $y_i$ empty seats:
   • If $x_i \le y_i$, all waiting students will sit in the empty seats. At this point, there are no students waiting in the $i$-th area, and $y_i - x_i$ empty seats remain.
   • If $x_i > y_i$, exactly $y_i$ waiting students will sit in all the empty seats. At this point, $x_i - y_i$ students remain waiting in the $i$-th area, and there are no empty seats remaining.
2. All students currently waiting in each area will simultaneously move to the next area. Specifically, all students waiting in the $i$-th area will move to the $(i \pmod n) + 1$-th area.

Among these students, exactly $k$ students left the cafeteria immediately upon opening because they were in a hurry. Ecrade does not know which areas these $k$ students were in. He wants to know, among all possible distributions of these $k$ students, what is the minimum number of moments that must pass after the cafeteria opens such that there are no students waiting in any area.

Input

The input is read from standard input. The first line contains an integer $T$ ($1 \le T \le 5 \times 10^5$), representing the number of test cases. For each test case: The first line contains two integers $n, k$ ($1 \le n \le 5 \times 10^5$). The second line contains $n$ integers $a_1, a_2, \dots, a_n$ ($1 \le a_i \le 10^9$). * The third line contains $n$ integers $b_1, b_2, \dots, b_n$ ($1 \le b_i \le 10^9$).

It is guaranteed that $0 \le k \le \sum_{i=1}^n a_i \le \sum_{i=1}^n b_i$, and the sum of $n$ over all test cases does not exceed $5 \times 10^5$.

Output

For each test case, output a single integer on a new line representing the answer.

Examples

Input 1

4
3 0
1 1 4
5 1 4
4 0
1 2 3 4
4 3 2 1
3 6
1 1 4
5 1 4
4 1
1 2 3 4
4 3 2 1

Output 1

1
4
0
2

Note

For convenience, we use arrays $a$ and $b$ to denote the number of students waiting and the number of remaining empty seats in each area after each moment.

For the first test case, no students leave the cafeteria: * After the first moment, $a = [0, 0, 0], b = [4, 0, 0]$.

For the second test case, no students leave the cafeteria: After the first moment, $a = [3, 0, 0, 1], b = [3, 1, 0, 0]$; After the second moment, $a = [1, 0, 0, 0], b = [0, 1, 0, 0]$; After the third moment, $a = [0, 1, 0, 0], b = [0, 1, 0, 0]$; After the fourth moment, $a = [0, 0, 0, 0], b = [0, 0, 0, 0]$.

For the third test case, all students leave the cafeteria.

For the fourth test case, only one student leaves the cafeteria: If this student is in the 1st area, $a$ becomes $[0, 2, 3, 4]$: After the first moment, $a = [3, 0, 0, 1], b = [4, 1, 0, 0]$; After the second moment, $a = [1, 0, 0, 0], b = [1, 1, 0, 0]$; After the third moment, $a = [0, 0, 0, 0], b = [0, 1, 0, 0]$. If this student is in the 2nd area, $a$ becomes $[1, 1, 3, 4]$: After the first moment, $a = [3, 0, 0, 1], b = [3, 2, 0, 0]$; After the second moment, $a = [1, 0, 0, 0], b = [0, 2, 0, 0]$; After the third moment, $a = [0, 1, 0, 0], b = [0, 2, 0, 0]$; After the fourth moment, $a = [0, 0, 0, 0], b = [0, 1, 0, 0]$. If this student is in the 3rd area, $a$ becomes $[1, 2, 2, 4]$: After the first moment, $a = [3, 0, 0, 0], b = [3, 1, 0, 0]$; After the second moment, $a = [0, 0, 0, 0], b = [0, 1, 0, 0]$. If this student is in the 4th area, $a$ becomes $[1, 2, 3, 3]$: After the first moment, $a = [2, 0, 0, 1], b = [3, 1, 0, 0]$; After the second moment, $a = [1, 0, 0, 0], b = [1, 1, 0, 0]$; After the third moment, $a = [0, 0, 0, 0], b = [0, 1, 0, 0]$. * Therefore, when this student is in the 3rd area, it takes at least 2 moments to ensure there are no students waiting in any area.