import java.util.*; import java.io.*; class Main { public static void main(String[] args) throws Exception { new Main().run(); } void run() { Scanner sc = new Scanner(System.in); int T=sc.nextInt(); for(int i=0;i map=new HashMap<>(); long mul=1; for(int r=0;r<=v;++r){ map.put(mul,r); mul=mul*g%p; } long g2=pow(inv(g,p),v,p); mul=1; for(int q=0;q<=v;++q){ if(map.containsKey(a*mul%p)){ return (q*v%(p-1)+map.get(a*mul%p))%(p-1); } mul=mul*g2%p; } throw new AssertionError(); } long primitiveRoot(long p){ for(long i=1;i0) { long q=a/b; a%=b; u-=v*q%p; u%=p; { u^=v;v^=u;u^=v; a^=b;b^=a;a^=b; } } return (u%p+p)%p; } long pow(long a,long n,long p){ n%=p-1; long r=1; for(;n>0;n>>=1,a=a*a%p)if(n%2==1)r=r*a%p; return r; } long gcd(long a,long b) { return a==0?b:gcd(b%a,a); } static void tr(Object... objects) { System.out.println(Arrays.deepToString(objects)); } }