题目描述

有两个巨人 Bea（一号）和 Ver（二号）在玩游戏。每个人都有自己的山脉。

你已经测量了这些山脉的高度：Bea 的山脉高度从左到右依次为 $a_1, a_2, \dots, a_n$，Ver 的山脉高度从右到左依次为 $b_1, b_2, \dots, b_m$。游戏开始时，两个巨人都站在各自编号为 $1$ 的山上。因此，他们面对面站立，并且能看到自己和对手所有的山。这两位巨人是懂得审美的，所以他们的山脉高度都是非递增排列的，即 $a_i \ge a_{i+1}$（$1 \le i < n$），$b_i \ge b_{i+1}$（$1 \le i < m$）。

在下面的插图中展示了一个初始排列的示例：Bea 的山脉为 $3, 2, 1$，Ver 的山脉为 $4, 2$。为了简单起见，山脉被描绘成矩形，两个巨人被绘成海狸，Bea 的在左侧，Ver 的在右侧。

两个巨人轮流进行操作，Bea 先手。 在每个回合中，轮到的巨人会执行以下行动：

1. 拿起一块巨石砸向对手当前所站立的山，导致对手当前所在山的高度减 $1$。
2. 随后，该巨人会观察自己当前的状况：如果他发现正前方（即编号比当前大 $1$）的山的高度严格大于他当前所在的山的高度，他就会跳到下一座山上。
3. 如果该巨人发现自己站在平地上（当前所在山的高度变为 $0$），并且他前方已经没有更多的山了（即他站在自己的最后一座山上），他就会认输。

由于山的高度很高且数量众多，游戏可能会持续很长时间。你需要判断谁将赢得游戏。

输入格式

第一行包含一个整数 $t$（$1 \le t \le 500$）—— 测试用例的数量。

对于每个测试用例：

• 第一行包含两个整数 $n$ 和 $m$（$1 \le n, m \le 100$）—— 分别表示第一个巨人（Bea）和第二个巨人（Ver）的山脉数量。
• 第二行包含 $n$ 个整数 $a_1, a_2, \dots, a_n$（$1 \le a_i \le 10^9$；$a_i \ge a_{i+1}$）—— 表示第一个巨人的山脉高度。
• 第三行包含 $m$ 个整数 $b_1, b_2, \dots, b_m$（$1 \le b_i \le 10^9$；$b_i \ge b_{i+1}$）—— 表示第二个巨人的山脉高度。

输出格式

对于每个测试用例，输出一行一个整数：1 表示第一个巨人 (Bea) 获胜，2 表示第二个巨人 (Ver) 获胜。

样例输入 1

6
1 1
1
1
1 1
1
2
1 2
4
4 1
4 2
4 3 2 1
10 1
4 2
4 3 2 1
6 5
4 2
4 3 2 1
7 5

样例输出 1

1
2
2
2
1
2

说明

样例解释

• 在第 $1$ 个测试用例中，在 Bea 的第一回合，他就会把 Ver 唯一的山的高度降为 $0$ 并最终获胜。
• 在第 $2$ 个测试用例中，Bea 会将 Ver 的山高度降为 $1$，随后在下个回合 Ver 会获胜。
• 在第 $3$ 个测试用例中，在前 $3$ 个回合期间，Bea 和 Ver 所在的山的高度都会降为 $1$。然后 Bea 会将 Ver 所在山的高度降为 $0$，但是 Ver 还有一座山，所以在 Ver 的回合，他会跳到下一座山上，并通过将 Bea 唯一的山高度降为 $0$ 来赢得比赛。

数据范围

• 对于所有测试点，保证 $1 \le t \le 500$。
• 对于每个测试用例，保证 $1 \le n, m \le 100$。
• 对于每个测试用例，保证 $1 \le a_i, b_i \le 10^9$ 且序列单调不增。
• 保证所有的输入数值均为整数。