#include <iostream>
#include <cctype>
#include <cmath>
#include "inv.h"
typedef unsigned ui;
typedef __uint128_t L;
typedef unsigned long long ull;
const ui M1 = 1000, M2 = M1 * M1;
ui T, m1, m2, MOD, len, fra[M2 + 5], invs[M2 + 5], sum[M2 + 5];
ui q[M2 + 5];
ull p[M2 + 5];
double invm1, INV;
char buf[1 << 22 | 1], *p1 = buf;
inline char Getchar()
{
    return *p1 == '\0' && (std::cin.read(p1 = buf, 1 << 22)), *p1++;
}
struct FastMod
{
    ull b, m;
    FastMod(ull b) : b(b), m(ull((L(1) << 64) / b)) {}
    friend inline ull operator%(const ull &a, const FastMod &mod)
    {
        ull r = a - (L(mod.m) * a >> 64) * mod.b;
        return r >= mod.b ? r - mod.b : r;
    }
} mod(2);
inline ull abs(const ull &a)
{
    return a >> 63 ? -a : a;
}
inline ui read()
{
    ui n(0);
    char s;
    while (!isdigit(s = Getchar()))
        ;
    while (n = n * 10 + (s & 15), isdigit(s = Getchar()))
        ;
    return n;
}
inline void init()
{
    ui i, j, x;
    for (i = 1; i ^ m1; ++i)
    {
        const double &INV = 1. / i + 1e-15;
        for (j = 0; j ^ i; ++j)
        {
            if (!sum[x = 1ull * j * m2 * INV])
            {
                sum[x] = 1, fra[x] = m1 * i + j;
            }
        }
    }
    for (i = 0; i <= m2; ++i)
    {
        if (sum[i])
            ++len, q[len] = fra[i] * invm1, p[len] = 1ull * (fra[i] - q[len] * m1) * MOD;
        if (i)
        {
            sum[i] += sum[i - 1];
        }
        invs[i] = i > 1 ? 1ull * (MOD - MOD / i) * invs[MOD % i] % mod : i;
    }
}
inline ui Inv(const ui &a)
{
    static ui q, k;
    static ull t;
    if (a <= m2)
        return inv[a];
    if (MOD - a <= m2)
        return MOD - inv[MOD - a];
    k = sum[ui(a * INV)];
    if (k <= len)
    {
        q = ::q[k];
        t = 1ull * a * q - p[k];
        if (abs(t) <= m2)
            return 1ull * q * (t >> 63 ? MOD - invs[-t] : invs[t]) % mod;
    }
    if (++k <= len)
    {
        q = ::q[k];
        t = 1ull * a * q - p[k];
        if (abs(t) <= m2)
            return 1ull * q * (t >> 63 ? MOD - invs[-t] : invs[t]) % mod;
    }
    return -1;
}
// int main()
// {
//     std::ios::sync_with_stdio(false);
//     std::cin.tie(0);
//     std::cout.tie(0);
//     ui k, x, sum(0);

//     T = read();
//     MOD = read();

//     mod = FastMod(MOD);
//     m1 = pow(MOD, 1. / 3) + 1;
//     m2 = m1 * m1;
//     invm1 = 1. / m1 + 1e-15;
//     INV = 1. * m2 / MOD + 1e-15;
//     init();

//     while (T--)
//     {
//         std::cout << Inv(read()) << "\n";
//     }
// }
void init(int p)
{
    MOD = p;
    mod = FastMod(MOD);
    init();
}
int inv(int x)
{
    return Inv(x);
}

implementer.cpp: In function ‘int main()’:
implementer.cpp:22:14: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
   22 |         scanf("%d", &n);
      |         ~~~~~^~~~~~~~~~
answer.code: In function ‘ui Inv(const ui&)’:
answer.code:72:21: warning: pointer to a function used in arithmetic [-Wpointer-arith]
   72 |         return inv[a];
      |                     ^
answer.code:72:21: error: invalid conversion from ‘int (*)(int)’ to ‘ui’ {aka ‘unsigned int’} [-fpermissive]
   72 |         return inv[a];
      |                     ^
      |                     |
      |                     int (*)(int)
answer.code:74:33: warning: pointer to a function used in arithmetic [-Wpointer-arith]
   74 |         return MOD - inv[MOD - a];
      |                                 ^
answer.code:74:20: error: invalid operands of types ‘ui’ {aka ‘unsigned int’} and ‘int(int)’ to binary ‘operator-’
   74 |         return MOD - inv[MOD - a];
      |                ~~~ ^ ~~~~~~~~~~~~
      |                |                |
      |                |                int(int)
      |                ui {aka unsigned int}