输入描述:

第一行输入一个正整数  ，表示询问次数。

接下来  行，每行输入两个正整数  ，表示询问。

输出描述:

对于每个询问，在一行中输出一个整数表示答案。由于这个答案可能很大，因此你需要输出答案对  取模后的结果。