static bool coprime(long u, long v)
{
    if (((u | v) & 1) == 0) return false;

    while ((u & 1) == 0) u >>= 1;
    if (u == 1) return true;

    do
    {
        while ((v & 1) == 0) v >>= 1;
        if (v == 1) return true;

        if (u > v) { long t = v; v = u; u = t; }
        v -= u;
    } while (v != 0);

    return false;
}

template<class T>
inline T gcd(T a, T b) {
    while(b) {
        auto t = a % b;
        a = b;
        b = t;
    }
    return a;
}

template<class T>
inline bool are_coprimes(T a, T b) {
    if(!((a | b) & 1))
        return false; // Both are even numbers, divisible by at least 2.
    return 1 == gcd(a, b);
}

inline unsigned gcd(unsigned u, unsigned v)
{
    auto shift = __builtin_ctz(u | v);
    u >>= __builtin_ctz(u);
    do {
        v >>= __builtin_ctz(v);
        if(u > v)
            std::swap(u, v);
    } while((v -= u));
    return u << shift;
}