人生的赌注Ⅱ

“为什么要隐藏起来呢？”

“其实是想有人问起吗？”

“我绝对不会笑的，要不要聊聊呢。”

“不说出口什么都不会明白。”

“只是放在心里谁都不会懂。”

“真是麻烦的生物呢，人类这种东西。”

Hello,How are u.

题目做累了就来听听歌吧ハロ／ハワユ

想来一场关于人生的赌注吗？现在你面前有一个圆盘，上面被均匀的分成了n块扇形区域并分别编号1-n，在12点钟处有指针，如果你愿意你就可以选择旋转这个圆盘，如果最后指针停在了标号k处，如果k满足k能够被它的立方根的底整除，即

那么我将会给予你一份勇气，否则我会从你的脑海中夺走一份记忆。

你只有一次机会，现在你想知道会获得勇气的期望。

单组数据。

第一行一个整数q(q<=1e5)——代表下面有q轮赌注。

接下来q行每行两个整数n，Mod(0 < n,Mod <= 1e18)——代表每轮赌注圆盘上的扇形数与模数。

保证n⊥Mod

对于每轮赌注，输出获得勇气的期望值ans，因为他可能是一个小数，所以请将答案模Mod后输出

p.s. p/q%Mod = p*(q^-1)%Mod

1
2 1000000007

1