Bash 玩函数

• 时间限制：3 秒
• 内存限制：256 MiB

题目描述

定义 $f_0(n)$ 为满足 $pq=n$ 且 $\gcd(p,q)=1$ 的有序正整数对 $(p,q)$ 的数量。

递归定义

其中 $(u,v)$ 枚举所有满足 $uv=n$ 的有序正整数对，不要求互质。

给定若干个 $(r,n)$，求 $f_r(n)$ 对 $10^9+7$ 取模的结果。

输入格式

第一行一个整数 $q$。接下来 $q$ 行，每行两个整数 $r,n$。

输出格式

对每个询问输出一行一个答案。

样例输入 1

5
0 30
1 25
3 65
2 5
4 48

样例输出 1

8
5
25
4
630

数据范围

• $1\le q\le10^6$；
• $0\le r\le10^6$；
• $1\le n\le10^6$。

计分方式

本题按测试点独立计分，同子任务内测试点等分。