def f(s, d)
    return 0 if s == d
    return f(-d, -s) if d <= 0
    return f(0, -s) + f(0, d) if s < 0
    return d.to_s(2).count(?1) if s == 0
    k = s.to_s(2).size
    l = d.to_s(2).size
    return f(s - (1 << k - 1) , d - (1 << l - 1)) if k == l
    sprintf("%0#{l}b", s).count(?0) - (s & (s ^ (s - 1))).to_s(2).size + d.to_s(2).count(?1)
end

n = gets.to_i
n.times do
    s, d= gets.split.map(&:to_i)
    p f(s, d)
end

