rumour.cpp

#include <cstdint>
#include <iostream>

#ifdef _MSC_VER
#include <intrin.h>
#define clz(x) __lzcnt64(x)
#else
#define clz(x) __builtin_clzll(x)
#endif

using u64 = std::uint64_t;

u64 TreeDist(u64 a, u64 b) {
    if (a < b)
        std::swap(a, b);
    u64 ms_one = clz(b) - clz(a);
    u64 x = (a >> ms_one) ^ b;
    // clz on 0 is undefined, gcc returns 63
    if (x)
        x = 2 * (64 - clz(x));
    return x + ms_one;
}

int main() {
    unsigned q = 0;
    std::cin >> q;

    for (unsigned i = 0; i < q; ++i) {
        std::uint64_t a, b;
        std::cin >> a >> b;
        std::cout << TreeDist(a, b) << '\n';
    }

    return 0;
}