Préférence 是一种在东欧非常流行的纸牌游戏。它通常使用一副 32 张牌的牌组，包含四种花色（黑桃、梅花、方块和红桃），每种花色有从 7 到 10 的点数牌，以及 J、Q、K 和 A。在每一轮游戏中，三名玩家每人获得十张牌，桌上留下两张牌作为底牌。随后进入叫牌阶段，玩家进行叫牌，即承诺至少赢得一定数量的墩数。叫牌的一种特殊情况被称为 misère，即承诺无论其他玩家如何出牌，自己都不赢得任何一墩。

在本题中，我们考虑一种 préférence 的特殊变体，它使用一副包含 $A \cdot B$ 张牌的修改版牌组，其中 $A$ 是花色数量，$B$ 是每种花色的点数数量。例如，标准的 32 张牌 préférence 牌组有 $A = 4$ 种花色和 $B = 8$ 个点数。为方便起见，我们将花色编号为 $1$ 到 $A$，点数编号为 $1$ 到 $B$。

你需要解决一个关于这种 préférence 变体的谜题。在这种变体中，如果对于每一种花色，当我们把你手中属于该花色的牌按点数从小到大排序为 $b_1 < b_2 < \dots < b_k$（其中 $k$ 是你手中该花色的牌数）时，满足条件 $b_i \le 2i - 1$（对于所有 $1 \le i \le k$），我们就称该手牌为“保证 misère”。如果你手中没有某种花色的牌（$k = 0$），则该条件平凡满足。

你手中现在有 $n$ 张牌，你可以选择任意 $x$ 张你没有的牌加入手中。然后，你必须从手中的 $n+x$ 张牌中选出任意 $x$ 张丢弃，使手中剩余 $n$ 张牌。你的任务是找到最小的 $x$，使得你可以将手牌转换为“保证 misère”的状态。

输入格式

每个测试包含多个测试用例。第一行包含测试用例的数量 $t$ ($1 \le t \le 1000$)。接下来是各测试用例的描述。

每个测试用例的第一行包含三个整数 $n, A, B$，分别表示你手中的牌数、牌组中的花色数量和每种花色的点数数量 ($1 \le n \le 5000; 1 \le A, B \le 10^9$)。

接下来的 $n$ 行，每行包含两个整数 $a_i$ 和 $b_i$，描述一张牌，其中 $a_i$ 是第 $i$ 张牌的花色，$b_i$ 是其点数 ($1 \le a_i \le A; 1 \le b_i \le B$)。你手中的所有牌各不相同。

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

输出格式

对于每个测试用例，输出最小的非负整数 $x$，使得你可以通过先添加 $x$ 张你没有的牌，再丢弃 $x$ 张牌，将手牌转换为“保证 misère”的状态。

可以证明这样的 $x$ 总存在。

样例

样例输入 1

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

样例输出 1

1
2