AT_arc221_a [ARC221A] Two Arithmetic Progressions

You are given positive integers $ N,A,B,C,D $ . Find $ \displaystyle \sum_{i=1}^N \gcd (Ai+B,Ci+D) $ , modulo $ 998244353 $ . Here, $ \gcd(x,y) $ denotes the greatest common divisor of $ x $ and $ y $ . You are given $ T $ test cases; solve each of them.

The input is given from Standard Input in the following format: > $ T $ $ \text{case}_1 $ $ \text{case}_2 $ $ \vdots $ $ \text{case}_T $ Each test case is given in the following format: > $ N $ $ A $ $ B $ $ C $ $ D $

Output the answers for the test cases in order, separated by newlines.

### Sample Explanation 1 For the first test case, the answer is $ \gcd(4,6)+\gcd(5,10)+\gcd(6,14)+\gcd(7,18)=2+5+2+1=10 $ . ### Constraints - $ 1\leq T\leq 200 $ - $ 1\leq N\leq 10^9 $ - $ 1\leq A,B,C,D\leq 10^4 $ - All input values are integers.