给定一个单词集合D，能够使用HASH快速判断字符串q 是否在D中。假定我们使用大小为n的哈希表T，表中每一个位置可以存储一个字符串，另使用两个函数 h₁ 和 h₂，h₁ 和 h₂都能将任意字符串映射到0到n-1。在向哈希表插入字符串d时，T[h₁(d)]为空，置T[h₁(d)] = d，否则如果T[h₂(d)]为空，置T[h₂(d)] = d。如果两个位置都被占据了，则将占据T[h₁(d)]的字符串r拿出，置T[h₁(d)] = d。然后尝试将r按照上述规则尝试放在另一位置上，即如果T[h₂(r)]为空，置T[h₂(r)] = r，否则取出T[h₂(r)]，并置T[h₂(r)] = r。如果产生了死循环，则取消之前的操作，最开始的字符串d取代T[h₂(d)]，如果仍会导致死循环，表示需要重新选取HASH函数。

第一行有一个正整数 t ，表示数据组数(不多于50)。每组数据第一行有两个整数， m 和n，1 ≤ m ≤ n ≤ 10000 ， m 是需要插入HASH表的字符串个数，n是HASH表的大小。接下来的m行中，每行有两个整数，第i行描述了第i个单词的HASH函数值h₁(d_i)和h₂(d_i)。两个数值可能相等。

2
3 3
0 1
1 2
2 0
5 6
2 3
3 1
1 2
5 1
2 5

successful hashing
rehash necessary