Description

最近，铭铭迷恋上了一种项链。与其他珍珠项链基本上相同，不过这种项链的珠子却与众不同，是正三菱柱的泰山石雕刻而成的。

三菱柱的侧面是由正方形构成的，每个侧面都刻有数字。能够让铭铭满意的项链必须满足以下条件：

1. 这串项链由 $n$ 颗珠子构成。

2. 每一个珠子上面的每个数字 $x$，必须满足 $0<x\le a$，且珠子上面三个数字的最大公约数要恰好为 $1$。

3. 相邻的两个珠子必须不同。两个珠子被认为是相同的，当且仅当它们经过旋转，或者翻转后能够变成一样的。

4. 两串项链如果能够经过旋转变成一样的，那么这两串项链被认为是相同的。

铭铭很好奇如果给定 $n$ 和 $a$，能够找到多少串不同的项链。由于答案可能很大，所以输出答案模上 $10^{9}+7$ 的值。

Input Format

本题有多组数据。

第一行给定一个整数 $T$，表示数据组数。
接下来 $T$ 行，每行两个整数 $n$ 和 $a$。

Output Format

对于每组数据输出一个整数，表示有多少串不同的项链。

1
2  2

3

Hint

满足条件的珠子共有三种：[1,1,1],[1,1,2],[1,2,2]。

组成的满足条件的串有：[1,2],[1,3],[2,3]。

对于 $100\%$ 的数据，保证 $1 \le T \le 10$，$2 \le n \le 10^{14}$，$1 \le a \le 10^7$。