#!/usr/bin/env python3
import subprocess,time
code = r'''#include <stdio>
#include <vector>
#include <algorithm>
#include <numeric>
#include <cstdint>
using namespace std;
using u64 = uint64_t;
using u128 = __uint128_t;
u64 mulmod(u64 a, u64 b, u64 m) { return (u128)a*b%m; }
u64 powmod(u64 a, u64 e, u64 m) { u64 r=1; while(e) { if(e&1) r=mulmod(r,a,m); a=mulmod(a,a,m); e>>=1; } return r; }
bool isPrime(u64 n) {
 if(n<2) return false;
 static u64 sp[]={2,3,5,7,11,13,17,19,23,29,31,37};
 for(u64 p:sp) if(n%p==0) return n==p;
 u64 d=n-1,s=0; while(!(d&1)) {d>>=1; s++;}
 static u64 bases[]={2,325,9375,28178,450775,9780504,1795265022};
 for(u64 a:bases) {
  if(a%n==0) continue;
  u64 x=powmod(a%n,d,n);
  if(x==1 || x==n-1) continue;
  bool ok=false;
  for(u64 r=1;r<s;++r) { x=mulmod(x,x,n); if(x==n-1) {ok=true; break;} }
  if(!ok) return false;
 }
 return true;
}
u64 seed=88172645463325252ULL;
u64 rnd() { seed^=seed<<7; seed^=seed>>9; return seed; }
u64 step(u64 x,u64 c,u64 n) { return (mulmod(x,x,n)+c)%n; }
u64 rho(u64 n) {
 if(n%2==0) return 2; if(n%3==0) return 3; if(n%5==0) return 5;
 for(