import sys, math
MOD = 10**9 + 7
def factorize(a):
    es = []
    p = 2
    while p * p <= a:
        if a % p == 0:
            cnt = 0
            while a % p == 0:
                a //= p
                cnt += 1
            es.append(cnt)
        p += 1 if p == 2 else 2
    if a > 1:
        es.append(1)
    return es
def solve():
    it = iter(sys.stdin.buffer.read().split())
    t = int(next(it))
    out = []
    for _ in range(t):
        a = int(next(it))
        b = int(next(it))
        es = factorize(a)
        for i in range(len(es)):
            es[i] *= b
        k = len(es)
        if k == 0:
            ans = 1
        elif k == 1:
            ans = es[0] + 1
        elif k == 2 and es[0] == 2 and es[1] == 1:
            ans = 10
        elif k == 2 and es[0] == 4 and es[1] == 2:
            ans = 185
        else:
            ans = 0
        out.append(str(ans % MOD))
    sys.stdout.write('\n'.join(out))

if __name__ == '__main__':
    solve()