#include <iostream>
#include <stdio.h>

int GetGenerator(int g, int p, int publicKey)
{
  if(g==1 && g!=publicKey)
    return -1;
  
  int i=0,curVal=g;
  for(i=1; i<p-1 && curVal!=publicKey; ++i)
      curVal= (curVal*g)%p;

  return i<p-1 ? i : -1;
}

int main()
{
  printf("%d\n", GetGenerator(106, 24691, 12375));
  return 0;
}