Sakiko有两个数字 ，她想知道，有多少种方式可以将 拆成 个正整数的乘积。 例如 时，有 这 4 种方法。 由于这个答案可能很大，因此你需要输出答案对 取模后的结果。

输入描述:

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

输出描述:

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