def variancja_z_powtorzeniami(b,n):
    import math
    a = int(math.sqrt(b)//1)
    p = n**a
    ans = 1
    r = b-a**2
    for x in range(a):
        ans*=p
    if r!=0:
        if r<10:
            for x in range(r):
                ans*=n
        else:
            variancja_z_powtorzeniami(r,n)
    return ans
 
d = int(input())
for x in range(d):
    K,N = input().split(" ")
    b = int(K) - 1
    n = int(N)
    if b==0:
        print(n)
    else :
        ans = variancja_z_powtorzeniami(b,n)
        ans*=(n-1)
        print(ans)
 

ZGVmIHZhcmlhbmNqYV96X3Bvd3RvcnplbmlhbWkoYixuKToKICAgIGltcG9ydCBtYXRoCiAgICBhID0gaW50KG1hdGguc3FydChiKS8vMSkKICAgIHAgPSBuKiphCiAgICBhbnMgPSAxCiAgICByID0gYi1hKioyCiAgICBmb3IgeCBpbiByYW5nZShhKToKICAgICAgICBhbnMqPXAKICAgIGlmIHIhPTA6CiAgICAgICAgaWYgcjwxMDoKICAgICAgICAgICAgZm9yIHggaW4gcmFuZ2Uocik6CiAgICAgICAgICAgICAgICBhbnMqPW4KICAgICAgICBlbHNlOgogICAgICAgICAgICB2YXJpYW5jamFfel9wb3d0b3J6ZW5pYW1pKHIsbikKICAgIHJldHVybiBhbnMKCmQgPSBpbnQoaW5wdXQoKSkKZm9yIHggaW4gcmFuZ2UoZCk6CiAgICBLLE4gPSBpbnB1dCgpLnNwbGl0KCIgIikKICAgIGIgPSBpbnQoSykgLSAxCiAgICBuID0gaW50KE4pCiAgICBpZiBiPT0wOgogICAgICAgIHByaW50KG4pCiAgICBlbHNlIDoKICAgICAgICBhbnMgPSB2YXJpYW5jamFfel9wb3d0b3J6ZW5pYW1pKGIsbikKICAgICAgICBhbnMqPShuLTEpCiAgICAgICAgcHJpbnQoYW5zKQo=

MTAKMSAxMAoyIDEwCjMgMwo0IDIKMyAxMAo0IDEwCjUgMTAKNiAxMAo3IDEwCjggMTA=

10
1 10
2 10
3 3
4 2
3 10
4 10
5 10
6 10
7 10
8 10