AT_arc221_a [ARC221A] Two Arithmetic Progressions

正整数 $ N,A,B,C,D $ が与えられます． $ \displaystyle \sum_{i=1}^N \gcd (Ai+B,Ci+D) $ を $ 998244353 $ で割った余りを求めてください．ただし， $ \gcd(x,y) $ で $ x $ と $ y $ の最大公約数を表します． $ T $ 個のテストケースが与えられるので，それぞれについて答えを求めてください．

入力は以下の形式で標準入力から与えられる． > $ T $ $ \text{case}_1 $ $ \text{case}_2 $ $ \vdots $ $ \text{case}_T $ 各テストケースは以下の形式で与えられる． > $ N $ $ A $ $ B $ $ C $ $ D $

各テストケースに対する答えを順に改行区切りで出力せよ．

### Sample Explanation 1 $ 1 $ 番目のテストケースについて，答えは $ \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 $ - 入力される数値は全て整数