凯文是一名来自永眠镇的学生,目前正在上数学课,老师正在给他做除法练习。
黑板上写着两行正整数,每行包含 $$$ n $$$ 数字。第一行是 $$$ a_1, a_2, \ldots, a_n $$$,第二行是 $$$ b_1, b_2, \ldots, b_n $$$。
对于每个除法练习,Kevin 可以选择任意段 $$$ [l, r] $$$ 并找到 $$$ b_l, b_{l+1}, \ldots, b_r $$$ 中的最小值 $$$ x $$$。然后,他将 $$$ l \leq i \leq r $$$ 的每个 $$$ a_i $$$ 修改为 $$$ a_i $$$ 除以 $$$ x $$$ 的上限。
正式地,他选择两个整数 $$$ 1 \leq l \leq r \leq n $$$,设置 $$$ x = \min_{l \leq i \leq r} b_i $$$,并将 $$$ l \leq i \leq r $$$ 的所有 $$$ a_i $$$ 更改为 $$$ \lceil \frac{a_i}{x} \rceil $$$。
当所有 $$$ a_i $$$ 变成 $$$ 1 $$$ 时,Kevin 可以下课回家。他渴望离开,并想知道实现这一目标所需的最少除法练习次数。
输入
每个测试包含多个测试用例。第一行包含测试用例的数量 $$$ t $$$ ($$$ 1 \le t \le 10^4 $$$)。
每个测试用例的第一行包含一个整数 $$$ n $$$ ($$$ 1 \le n \leq 2 \cdot 10^5 $$$) — 序列 $$$ a $$$ 和 $$$ b $$$ 的长度。
每个测试用例的第二行包含 $$$ n $$$ 整数 $$$ a_1, a_2, \ldots, a_n $$$ ($$$ 1 \le a_i \le 10^{18} $$$) — 棋盘上的第一行整数。
每个测试用例的第三行包含 $$$ n $$$ 整数 $$$ b_1, b_2, \ldots, b_n $$$ ($$$ 2 \le b_i \le 10^{18} $$$) — 棋盘上的第二行整数。
保证所有测试用例的 $$$ n $$$ 之和不超过 $$$ 2 \cdot 10^5 $$$。
输出
对于每个测试用例,输出一个整数——离开课堂所需的最小除法练习数。
示例
输入 #1
3 3 5 4 2 6 3 2 5 3 6 1 3 2 3 5 3 2 2 6 8 3 3 7 5 8 3 2 3 4 2 3
输出 #1
2 3 3
注意
对于第一个测试用例:$$$ [{\color{red}{5,4}},2]\xrightarrow[\min(b_1,b_2)=3]{\text{操作段}[1,2]}[{\color{red}{2,2,2}}]\xrightarrow[\min(b_1,b_2,b_3)=2]{\text{操作段}[1,3]}[1,1,1]$$$。
对于第二个测试用例:$$$ [{\color{red}{3,6,1}},3,2]\xrightarrow[\min(b_1,b_2,b_3)=3]{\text{操作段}[1,3]}[1,{\color{red}{2,1,3}},2]\xrightarrow[\min(b_2,b_3,b_4)=2]{\text{操作段 }[2,4]}[1,1,1,{\color{red}{2,2}}]\xrightarrow[\min(b_4,b_5)=2]{\text{操作段}[4,5]}[1,1,1,1,1]$$$。