############################################################### #https://atcoder.jp/contests/abc180/submissions/70920858 import random from math import gcd def is_prime(n): if n<2: return False prime=[2,3,5,7,11,13] for p in prime: if n%p==0: return n==p d=n-1 s=0 while d%2==0: d//=2 s+=1 for a in [2,325,9375,28178,450775,9780504,1795265022]: if a%n==0: continue x=pow(a,d,n) if x==1 or x==n-1: continue for i in range(s-1): x=x*x%n if x==n-1: break else: return False return True def _rho(n): if n%2==0: return 2 if n%3==0: return 3 while True: y=random.randrange(2,n-1) c=random.randrange(1,n-1) m=128 g=1 r=1 q=1 x=0 while g==1: x=y for i in range(r): y=(y*y+c)%n k=0 while k