您和您的朋友 Ilya 正在参加由多个阶段组成的个人编程竞赛。参赛者在每个阶段可以获得 $$$0$$$ 到 $$$100$$$ 积分(含),与其他参赛者无关。
Points received by contestants in different stages are used for forming overall contest results.假设比赛已完成 $$$k$$$ 个阶段。对于每位参赛者,选择得分最高的 $$$k - \lfloor \frac{k}{4} \rfloor$$$ 阶段,并将这些分数相加。这个总和就是参赛者的总成绩。 (这里 $$$\lfloor t \rfloor$$$ 表示向下舍入 $$$t$$$。)
例如,假设已完成 $$$9$$$ 个阶段,并且您的分数为 $$$50, 30, 50, 50, 100, 10, 30, 100, 50$$$。首先,选择得分最高的 $$$7$$$ 阶段 - 例如,可以选择除 $$$2$$$-nd 和 $$$6$$$-th 之外的所有阶段。那么您的总结果等于 $$$50 + 50 + 50 + 100 + 30 + 100 + 50 = 430$$$。
到目前为止,$$$n$$$阶段已经完成,你知道你和伊利亚在这些阶段获得的分数。不过,目前还不清楚还会举办多少个阶段。您想知道最少的附加阶段数是多少,之后您的结果可能会大于或等于 Ilya 的结果,至少在理论上是这样。找到这个号码!
输入
每个测试包含多个测试用例。第一行包含测试用例的数量 $$$t$$$ ($$$1 \le t \le 1000$$$)。测试用例的描述如下。
The first line of each test case contains a single integer $$$n$$$ ($$$1 \le n \le 10^5$$$) — the number of completed stages.
第二行包含 $$$n$$$ 整数 $$$a_1, a_2, \ldots, a_n$$$ ($$$0 \le a_i \le 100$$$) - 您完成阶段的分数。
第三行包含 $$$n$$$ 整数 $$$b_1, b_2, \ldots, b_n$$$ ($$$0 \le b_i \le 100$$$) — Ilya 已完成阶段的分数。
保证所有测试用例的 $$$n$$$ 总和不超过 $$$10^5$$$。
输出
对于每个测试用例,打印一个整数 - 您的结果能够大于或等于 Ilya 的结果所需的最小附加阶段数。
如果您的结果已经不小于 Ilya 的结果,请打印 $$$0$$$。
示例
输入 #1
5 1 100 0 1 0 100 4 20 30 40 50 100 100 100 100 4 10 20 30 40 100 100 100 100 7 7 59 62 52 27 31 55 33 35 50 98 83 80 64
输出 #1
0 1 3 4 2
注意
在第一个测试用例中,您在第一阶段获得了 $$$100$$$ 分,而 Ilya 则获得了 $$$0$$$ 分。因此,您的总成绩 ($$$100$$$) 已经不低于 Ilya 的成绩 ($$$0$$$)。
In the second test case, you have scored $$$0$$$ points for the first stage, while Ilya has scored $$$100$$$. A single stage with an opposite result is enough for both your and Ilya's overall scores to become equal to $$$100$$$.
在第三个测试用例中,您的总结果是 $$$30 + 40 + 50 = 120$$$,而 Ilya 的结果是 $$$100 + 100 + 100 = 300$$$。经过三个额外阶段后,您的结果可能会变为 $$$420$$$,而 Ilya 的结果可能会变为 $$$400$$$。
在第四个测试用例中,四个附加阶段后的总体结果可能会等于 $$$470$$$,而 Ilya 的结果可能会等于 $$$400$$$。三个阶段还不够。