MINPIZZAS.py

ans = []
def func():
  for _ in range(int(input())):
    data = [int(x) for x in input().split()]
    n = 1
    def test():
      nonlocal n
      if (n * data[1]) % data[0] == 0:
        ans.append(n)
      else:
        n += 1
        test()
    test()
  for x in ans:
    print(x)
func()