#include <stdio.h>
#include <stdlib.h>

typedef unsigned __int128 uint128;
typedef unsigned long long int uint64;

uint64 l[] = {
    4611686018427394499,
    4611686018427395927,
    4611686018427402023,
    4611686018427402599,
    4611686018427407519,
    4611686018427407939,
    4611686018427408827,
    4611686018427412487,
    4611686018427412619,
    4611686018427413183,
    4611686018427415163,
    4611686018427419483,
    4611686018427419627,
    4611686018427427067,
};

uint64 expm(uint64 m, uint64 e, uint64 mod)
{
    uint128 _r=1;
    uint128 _m=(uint64)m;
    uint128 _mod = (uint64)mod;
    
    while (e > 0) {
      if ((e & 1) > 0) _r = (_r * _m) % _mod;
      e >>= 1;
      _m = (_m * _m) % _mod;
   }

    return (uint64)_r;
}

uint64 generateur(uint64 p)
{
    uint64 g=2;
    uint64 r=1;

    while(g < p - 1) {
        r = expm(g, (p-1)/2, p);
        if(r != 1)
            return g;
        g++;
    }
    return 0;
}