int lut[512][512];
uint32_t faster_binary_gcd(uint32_t u, uint32_t v)
{
    auto zu = std::countr_zero(u);
    auto zv = std::countr_zero(v);
    auto shift = std::min(zu, zv);
    u >>= zu;
    v >>= zv;
    do
    {
        if (u < 512)
            return lut[u][v % u] << shift;
        uint32_t u_minus_v = u - v;
        if (u > v)
        {
            u = v, v = u_minus_v;
        }
        else
        {
            v = v - u;
        }
        v >>= std::countr_zero(u_minus_v);
    } while (v != 0);
    return u << shift;
}