import Data.List (intercalate)

-- a <= b

incr a b k
 | a `mod` k /= 0 = 0
 | b `mod` k /= 0 = x
 | a == k * k = 1
 | otherwise = 1 + x
 where x = if 0 == b `mod` (a `div` k) then 1 else 0

help a b k acc
 | k2 < a = help a b (k+1) $ next
 | k2 > a = acc
 | otherwise = next
 where k2 = k * k
       next = acc + incr a b k

common :: Int -> Int -> Int
common x y =
  let a = min x y
      b = max x y
    in help a b 1 0

foo s = let ws = map read $ words s in common (head ws) (ws !! 1)

main = do
  cont <- getContents
  putStrLn $ intercalate "\n" $ map (show . foo) $ tail $ lines cont