对于数组 ，我们定义它是好的，当且仅当：对于全部的 ， 总是成立； 现在，你可以选择 个整数组成一个数组，使得这个数组是好的；同时，你还需要保证： 数组中至少存在 个不同的数字； 数组中的每一个数字都满足 。 在这里， 代表取模。

输入描述:

每个测试文件均包含多组测试数据。第一行输入一个整数 代表数据组数，每组测试数据描述如下：在一行上输入两个整数 代表你需要挑选的数字数量、不相同数字个数的限制。

输出描述:

对于每一组测试数据，在一行上输出一个整数，代表满足条件的数组数量。