Background

Special for algorithm lovers, ^_^

Description

Ecrade_ 看着食堂里来回游走等位的人们陷入了沉思，于是他想到了这样一个问题。

食堂中共有 $n$ 个区域，在食堂即将开门时，第 $i$ 个区域中有 $a_i$ 名正在等位的学生和 $b_i$ 个空位。保证 $\sum\limits_{i=1}^{n}a_i\le \sum\limits_{i=1}^{n}b_i$。

食堂开门后的每个时刻，都会 依次 发生如下两个事件：

1. 每个区域中当前正在等位的学生都会尽可能地坐到该区域的空位上。 具体而言，假设第 $i$ 个区域中当前有 $x_i$ 名正在等位的学生和 $y_i$ 个空位。

   • 若 $x_i\le y_i$，那么所有正在等位的学生都会坐到空位上，此时第 $i$ 个区域中没有正在等位的学生，且会剩下 $y_i-x_i$ 个空位；
   • 若 $x_i>y_i$，那么会有恰好 $y_i$ 名正在等位的学生坐到所有空位上，此时第 $i$ 个区域中剩下 $x_i-y_i$ 名正在等位的学生，且没有剩余的空位。

2. 每个区域中当前正在等位的所有学生都会 同时 移动到下一个区域中。 具体而言，第 $i$ 个区域中所有正在等位的学生都会移动到第 $(i\bmod n) +1$ 个区域中。

在这群学生中，有恰好 $k$ 名学生因为赶时间上课，在食堂开门的瞬间就打包离开了。而 Ecrade_ 并不清楚这 $k$ 名学生都在哪些区域，所以他想知道，在这 $k$ 名学生所有可能的分布情况中，在食堂开门后，最少经过多少个时刻，就能够使得每个区域中都没有正在等位的学生。

Format

Input

第一行一个整数 $T\ (1\le T\le 5\times 10^5)$，表示测试数据组数。

对于每组测试数据：

• 第一行两个整数 $n,k\ (1\le n\le 5\times 10^5)$。
• 第二行 $n$ 个整数 $a_1,a_2,...,a_n\ (1\le a_i\le 10^9)$。
• 第三行 $n$ 个整数 $b_1,b_2,...,b_n\ (1\le b_i\le 10^9)$。

保证 $0\le k\le \sum\limits_{i=1}^n a_i\le \sum\limits_{i=1}^{n}b_i$，所有测试数据的 $n$ 的和不超过 $5\times 10^5$。

Output

对于每组测试数据，输出一行一个整数表示答案。

Samples

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

1
4
0
2

样例解释：

为方便表述，下直接用数组 $a,b$ 表示每个时刻后每个区域中正在等位的学生数以及剩余空位数。

• 第一组：无学生离开食堂。 第一个时刻后，$a=[0,0,0], b=[4,0,0]$。

• 第二组：无学生离开食堂。

  • 第 1 时刻：$a=[3,0,0,1], b=[3,1,0,0]$
  • 第 2 时刻：$a=[1,0,0,0], b=[0,1,0,0]$
  • 第 3 时刻：$a=[0,1,0,0], b=[0,1,0,0]$
  • 第 4 时刻：$a=[0,0,0,0], b=[0,0,0,0]$

• 第三组：所有学生离开食堂。

• 第四组：一名学生离开食堂。

  • 若该学生在第 3 个区域，则 $a$ 变为 $[1,2,2,4]$：

    • 第 1 时刻：$a=[3,0,0,0], b=[3,1,0,0]$
    • 第 2 时刻：$a=[0,0,0,0], b=[0,1,0,0]$ 此时最少 2 个时刻可完成。