def Primitive_Root(p): """Z/pZ上の原始根を見つける p:素数 """ if p==2: return 1 if p==998244353: return 3 if p==10**9+7: return 5 if p==163577857: return 23 if p==167772161: return 3 if p==469762049: return 3 fac=[] q=2 v=p-1 while v>=q*q: e=0 while v%q==0: e+=1 v//=q if e>0: fac.append(q) q+=1 if v>1: fac.append(v) g=2 while g