# def calc(n,k):
#     S = set()
#     for u in range(1<<n):
#         a = f"{u:b}".zfill(n)
#         b = []
#         for i in range(n):
#             cnt = 0
#             for j in range(k):
#                 cnt += a[(i+j)%n]=='1'
#             b.append(cnt)
#         S.add(tuple(b))
#     return len(S), S
# # while True:
# #     n = int(input())
# #     print([calc(n,i+1)[0] for i in range(n)])
# _,S = calc(6,3)
# S1={}
# for u in S:
#     v = tuple(u[(i+1)%6]-u[i] for i in range(6))
#     if v not in S1.keys():
#         S1[v] = [u]
#     else:
#         S1[v].append(u)

mod = 998244353
T = int(input())
for _ in range(T):
    n,k = map(int, input().split())
    from math import gcd
    g = gcd(n,k)
    t = pow(2,n//g,mod)-1
    ans = (pow(t,g,mod)+g*pow(t,g-1,mod))%mod
    print(ans)