def floor(x)
  x |= x >> 1
  x |= x >> 2
  x |= x >> 4
  x |= x >> 8
  x |= x >> 16
  (x + 1) >> 1
end

def f(a, b)
  t = floor(b - a)

  a, b = -b, -a if b % t == 0
  c = (b / t) * t
    
  b == c ? 1 : f(a, c) + f(c, b)
end

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