mod = 1000000007
eps = 10**-9


def main():
    import sys
    from math import gcd
    input = sys.stdin.readline

    T = int(input())
    for _ in range(T):
        N, C = map(int, input().split())
        ans = pow(C, 2*N, mod)
        for i in range(1, N):
            g = gcd(N, i)
            x = pow(C ** 2, g, mod)
            ans = (ans + x)%mod
        ans = (ans + pow(C, N, mod) * N)%mod
        #for i in range(N):
        #    g = gcd(N, i)
        #    x = pow(C, g, mod)
        #    ans = (ans + x)%mod
        ans = (ans * pow(2*N, mod-2, mod))%mod
        print(ans)


if __name__ == '__main__':
    main()