Inna 是一位狂热的徒步旅行者。她正在游览一系列共有 $n$ 座山峰的山脉，这些山峰的高度分别为 $h_1, h_2, \dots, h_n$。

在附近的一家商店里，Inna 发现了一本书，书中提到在过去某个时间点，这些山峰的高度按相同顺序分别为 $p_1, p_2, \dots, p_n$。然而，没有证据表明这本书有多久远。

书中还描述了一种侵蚀模型，使得山峰的高度逐年降低。每年，根据天气情况，会确定一个特定的高度阈值 $x$。然后，所有当前高度至少为 $x$ 的山峰高度都会减少恰好 $1$。不同年份的 $x$ 值可以不同。

Inna 对这本书的实际年代感到好奇，并想知道所描述的模型是否合理。请帮助她计算出侵蚀过程将山峰高度从 $p_1, p_2, \dots, p_n$ 变为 $h_1, h_2, \dots, h_n$（按相同顺序）所需的最少年份，如果根据给定的模型无法实现，则输出 $-1$。

输入格式

每个测试包含多个测试用例。第一行包含测试用例的数量 $t$ ($1 \le t \le 10^4$)。

接下来是各测试用例的描述。 每个测试用例的第一行包含一个整数 $n$，表示山峰的数量 ($1 \le n \le 10^5$)。 第二行包含 $n$ 个整数 $h_1, h_2, \dots, h_n$，表示山峰的当前高度 ($1 \le h_i \le 10^6$)。 第三行包含 $n$ 个整数 $p_1, p_2, \dots, p_n$，表示过去某个时间点山峰的高度 ($1 \le p_i \le 10^6$)。

保证所有测试用例的 $n$ 之和不超过 $10^5$。

输出格式

对于每个测试用例，输出将山峰高度从 $p_1, p_2, \dots, p_n$ 变为 $h_1, h_2, \dots, h_n$ 所需的最少年份，如果模型不成立，则输出 $-1$。

样例

样例输入 1

4
4
3 2 4 2
5 3 6 2
1
10
100000
5
1 2 3 4 5
1 2 3 4 5
3
1 4 6
4 1 8

样例输出 1

2
99990
0
-1

说明

在第一个测试用例中，山峰高度可以仅用两年时间从 $(5, 3, 6, 2)$ 变为 $(3, 2, 4, 2)$：

• 假设第一年 $x = 4$。这一年后，山峰高度变为 $(4, 3, 5, 2)$。
• 假设第二年 $x = 3$。这一年后，山峰高度变为 $(3, 2, 4, 2)$。