#Miller-Rabinの素数判定法 def Miller_Rabin_Primality_Test(N,Times=20): """Miller-Rabinによる整数Nの素数判定を行う. N:整数 ※:Trueは正確にはProbably Trueである(Falseは確定False). """ from random import randint as ri if N==2: return True if N==1 or N%2==0: return False q=N-1 k=0 while q&1==0: k+=1 q>>=1 for _ in range(Times): m=ri(2,N-1) y=pow(m,q,N) if y==1: continue flag=True for i in range(k): if (y+1)%N==0: flag=False break y*=y y%=N if flag: return False return True #ポラード・ローアルゴリズムによって素因数を発見する #参考元:https://judge.yosupo.jp/submission/6131 def Find_Factor_Rho(N): if N==1: return 1 from math import gcd m=1<<(N.bit_length()//8+1) for c in range(1,99): f=lambda x:(x*x+c)%N y,r,q,g=2,1,1,1 while g==1: x=y for i in range(r): y=f(y) k=0 while k1: if Miller_Rabin_Primality_Test(N): res.append([N,1]) N=1 else: j=Find_Factor_Rho(N) k=0 while N%j==0: N//=j k+=1 res.append([j,k]) if N>1: res.append([N,1]) res.sort(key=lambda x:x[0]) return res def Divisors_from_Prime_Factor(P,sorting=False): X=[1] for p,e in P: q=1 n=len(X) for _ in range(e): q*=p for j in range(n): X.append(X[j]*q) if sorting: X.sort() return X #================================================== Q=int(input()) for _ in range(Q): S,T=map(int,input().split()) if T%2==1: print(0) continue D=Divisors_from_Prime_Factor(Pollard_Rho_Prime_Factorization(S*S),True); M=len(D) E=[] for i in range(M): x=D[i] for j in range(i,M): y=D[j] if S*S