SP26561 PAIRDIV2 - Pair Divisible 2

Let $ C(N, a, b) $ be the number of integer pairs $ (x, y) $ in $ 1 \le x \le a $ , $ 1 \le y \le b $ such that $ xy $ is divisible by $ N $ . Given $ N $ , $ a $ and $ b $ , find $ C(N, a, b) $ **modulo** $ 10^{9} $ .

The first line contains $ T $ , the number of test cases. In each of the next $ T $ lines, you are given three numbers $ N $ , $ a $ and $ b $ .

For each test case, print $ C(N, a, b) $ **modulo** $ 10^{9} $ .