Description

一群怪物入侵了小镇。作为小镇的守护者，你需要保护小镇免受怪物的袭击。作为一名聪明的战士，你打算消灭其中一部分怪物，让剩下的怪物闻风丧胆、自行逃离小镇。

要击败一只怪物，你需要消耗 $a$ 点能量，而击败它之后你会恢复 $b$ 点能量。如果你攻击前的能量低于 $a$，你将会被消灭，小镇也会被摧毁。$a$ 和 $b$ 的数值因怪物而异。你可以任意选择要击杀的怪物，也可以按任意顺序击杀它们。

你想知道击杀至少 $k$ 只怪物所需的最少初始能量。你需要对所有 $k$ 计算答案。

Format

Input

输入的第一行包含一个整数 $t$（$1 \leq t \leq 10$），表示测试数据的组数。每组测试数据包含三行。

每组测试数据的第一行包含一个整数 $n$（$1 \leq n \leq 10^5$），表示怪物的数量。第二行包含 $n$ 个整数 $a_1, a_2, \ldots, a_n$（$0 \leq a_i \leq 10^9$），表示击败第 $i$ 只怪物所需的能量。第三行包含 $n$ 个整数 $b_1, b_2, \ldots, b_n$（$0 \leq b_i \leq 10^9$），表示击杀第 $i$ 只怪物后你恢复的能量。保证所有测试数据的 $n$ 之和不超过 $10^5$。

Output

设 $ans_k$ 为击败 $k$ 只怪物所需的最少初始能量。

你需要计算所有 $ans_k$（$1 \leq k \leq n$）。为了避免巨大的输出量，你只需要输出：

$$\sum_{k=1}^{n} \left( k \cdot ans_k \right) \bmod (10^9+7)$$

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

Samples

2
3
2 3 1
1 5 4
4
1 2 3 4
1 1 2 3

6
30

Hint

对于第一组测试数据，$ans = [1, 1, 1]$。

对于第二组测试数据，$ans = [1, 2, 3, 4]$。例如，当你有 $4$ 点初始能量时，你可以依次击杀第 $4$、第 $3$、第 $2$、第 $1$ 只怪物。首先击杀第 $4$ 只怪物，你的能量将变为 $4 - 4 + 3 = 3$。接着攻击第 $3$ 只怪物，能量变为 $3 - 3 + 2 = 2$。之后击杀第 $2$ 只，能量变为 $2 - 2 + 1 = 1$。最后你可以击杀第 $1$ 只，因为你的能量不低于 $a_1 = 1$。