题目描述

Preference 是一种在东欧较为流行的纸牌游戏。标准游戏通常使用 $32$ 张牌：四种花色，每种花色包含点数 $7$ 到 $10$、J、Q、K、A 共八个等级。

在每一局中，三名玩家各获得十张牌，另有两张牌作为底牌。随后进行叫牌，玩家承诺至少赢得一定数量的牌墩。一种特殊叫牌称为 misère，其目标是无论其他玩家怎样行动，自己都不能赢得任何一墩。

本题考虑一种修改版的游戏。牌堆中共有 $A\cdot B$ 张牌，其中：

• 有 $A$ 种花色，编号为 $1$ 到 $A$；
• 每种花色有 $B$ 个等级，编号为 $1$ 到 $B$。

定义一手牌能够保证 misère 成功，当且仅当对每一种花色均满足以下条件：

将手中该花色的牌按等级升序排列为

则对所有 $1\le i\le k$，都有

若手中没有该花色的牌，即 $k=0$，则该花色自动满足条件。

你当前手中有 $n$ 张牌。你可以选择任意 $x$ 张当前不在手中的牌，将它们加入手牌；随后从这 $n+x$ 张牌中任意丢弃 $x$ 张，使手牌数量重新变为 $n$。

请找出最小的非负整数 $x$，使得经过上述操作后，你的手牌能够保证 misère 成功。

输入格式

每个输入包含多组测试数据。

第一行包含一个整数 $t$，表示测试数据组数。

对于每组测试数据：

• 第一行包含三个整数 $n,A,B$，分别表示当前手牌数量、花色数和每种花色的等级数；
• 接下来 $n$ 行，第 $i$ 行包含两个整数 $a_i,b_i$，表示第 $i$ 张牌的花色和等级。

保证手中的所有牌互不相同。

数据范围

所有测试数据的 $n$ 之和不超过 $5000$。

输出格式

对于每组测试数据，输出最小的非负整数 $x$，使得可以先补入 $x$ 张当前不在手中的牌，再从手中丢弃任意 $x$ 张牌，最终得到一手能够保证 misère 成功的 $n$ 张牌。

可以证明，答案总是存在。

样例

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

1
2