该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

题目描述

LCR 当上了少女乐队社的指导老师，她要找一群女孩子组乐队。众所周知，一支乐队必须由五个人组成。已经有 $5-k$ 名少女主动报名，现在乐队还差 $k$（$2\le k\le 5$）个人。

学校里总共还有 $N$ 名少女可以组乐队，第 $i$ 个人擅长的乐器是 $a_i$，相性是 $b_i$。

LCR 需要招募 $k$ 名少女，她们擅长的乐器必须互不相同。

并且，少女的相性太接近不利于队内气氛，LCR 不希望这样。也就是说，假设选择的 $k$ 名少女的相性分别是 $b_1,b_2,b_3,\ldots,b_k$，那么，队内气氛的活跃度是 $\min_{i=1}^{k-1}\min_{j=i+1}^{k}|b_i-b_j|$，也就是少女们之间两两相性差（绝对值）的最小值。（原有的主动报名的成员不影响活跃度，只有这 $k$ 个人影响。）

现在，LCR 想组一个队内气氛最活跃的队伍，请你帮他计算出这个最活跃的气氛是多少。

输入格式

在文件 lotus.in 中读入。

第一行输入 $T$，表示一共 $T$ 组测试数据。

对于每组测试数据：

第一行三个正整数 $N,k,TP$，表示可选的人数，需求的人数，以及测试数据类型，$TP$ 有助于你识别这是哪一类测试数据。

接下来 $N$ 行，每行两个正整数 $a_i,b_i$，表示第 $i$ 名少女擅长的乐器以及相性值。

输出格式

在文件 lotus.out 中输出。

一个数字表示答案（最大可能的队内气氛活跃度），数据保证一定有解。

样例

样例输入 #1

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

样例输出 #1

2

样例 1 解释

选择第 $\{1,3,5\}$ 名少女，凑齐了三种不同的乐器 $a_1=1,a_3=3,a_5=2$，气氛是 $\min(|1-3|,|3-5|,|1-5|)=2$。

数据范围

测试点 $1\sim 2$：$N\leq 100$，$TP=1$。

测试点 $3\sim 6$：$N\leq 1000$，$k=5$，$1\leq a_i \leq 5$，$TP=2$。

测试点 $7\sim 10$：$N\leq 1000$，$k=5$，$TP=3$。

测试点 $11\sim 14$：$N\leq 10000$，$k=3$，$TP=4$。

测试点 $15\sim 17$：$N\leq 10000$，$k=5$，$1\leq a_i \leq 5$，$TP=5$。

测试点 $18\sim 20$：$TP=6$。

对于所有数据：$1\leq N \leq 10000$，$2\leq k \leq 5$，$1\leq a_i \leq N$，$1\leq b_i \leq 10^6$，$T\leq 5$。