K. 倍序数组

内存限制:32 MiB 时间限制:2000 ms 标准输入输出
题目类型:传统 评测方式:文本比较

题目描述

一个长度为 的正整数数组 被称为“倍序数组”当且仅当对于任意 ,都有 (其中 表示整除,即存在一个正整数 使得 )。请设计算法求出长度为 的倍序数组 的个数,且数组中每个元素满足 。因为答案可能很大,你只需要输出答案对 取模的结果。

输入格式

第一行一个正整数 ,表示数据组数。

接下来 行,每行两个正整数 ,表示数组长度和数组元素的最大值。

输出格式

对于每组数据,输出一行一个正整数,表示答案对 取模的结果。

样例

【样例输入】

2
2 3
3 4

【样例输出】

5
13

样例解释

第一组数据分别是

数据范围与提示

编辑器加载中 …
通告标题

通告内容

已知晓