ll pow(ll a, ll b, ll m)

 {

     a %= m;

     ll ans = ;

     while(b)

     {

         if(b & )ans = ans * a % m;

         a = a * a % m;

         b /= ;

     }

     return ans % m;

 }

 int tot;//素因子个数

 int a[];

 void get_fact(ll n)//质因数分解n

 {

     for(ll i = ; i * i <= n; i++)

     {

         if(n % i == )

         {

             a[tot++] = i;

             while(n % i == )n /= i;

         }

     }

     if(n != )a[tot++] = n;

 }

 bool g_test(ll g, ll p)//测试g是不是p的原根 此处p是素数 欧拉函数值为p - 1

 {

     for(ll i = ; i < tot; i++)

     {

         if(pow(g, (p - ) / a[i], p) == )return false;

     }

     return true;

 }

 int proot(ll p)

 //求解p最小原根，本题p为素数

 //返回最小的原根

 {

     get_fact(p - );//素数的欧拉函数值为p - 1

     int g = ;

     while()

     {

         if(g_test(g, p))return g;

         g++;

     }

 }