AT_past202209_i 毎日のリンゴ

$ T $ 個のテストケースについて、以下の問題を解いてください。 高橋君は「ルンルンマート」で使える $ M $ 円の商品券を $ 10^{100} $ 枚持っています。 この商品券を、購入する商品の金額に比べて過剰に使った場合でも、おつりが返ってくることはありません。 高橋君は、 $ i $ 日目に $ A \times i $ 円のリンゴを商品券のみを使って買います。 このとき、 $ A \times i $ 円以上を支払える最小の ( $ M $ 円の) 商品券の枚数を $ k $ 枚とすると、高橋くんの「悲しさ」が $ k \times M - A \times i $ だけ増加します。 この買い物を $ N $ 日続けたとき、高橋君の「悲しさ」の総和はいくつになりますか?

入力は以下の形式で標準入力から与えられる。 > $ T $ $ \rm{case}_1 $ $ \rm{case}_2 $ $ \dots $ $ \rm{case}_T $ ただし、 $ \rm{case}_i $ は $ i $ 番目のテストケースを表し、各テストケースは以下の形式で与えられる。 > $ N $ $ A $ $ M $

計 $ T $ 行出力せよ。 $ i $ 行目に $ i $ 番目のテストケースの答えを整数として出力せよ。

### Sample Explanation 1 この入力には、 $ 10 $ 個のテストケースが含まれています。 $ 1 $ 番目のケースでは、 $ N=4,A=5,M=8 $ です。 - $ 1 $ 日目には $ 5 $ 円のリンゴを買います。 $ 8 $ 円の商品券は $ 1 $ 枚必要で、このとき高橋君の「悲しさ」は $ 3 $ 増加します。 - $ 2 $ 日目には $ 10 $ 円のリンゴを買います。 $ 8 $ 円の商品券は $ 2 $ 枚必要で、このとき高橋君の「悲しさ」は $ 6 $ 増加します。 - $ 3 $ 日目には $ 15 $ 円のリンゴを買います。 $ 8 $ 円の商品券は $ 2 $ 枚必要で、このとき高橋君の「悲しさ」は $ 1 $ 増加します。 - $ 4 $ 日目には $ 20 $ 円のリンゴを買います。 $ 8 $ 円の商品券は $ 3 $ 枚必要で、このとき高橋君の「悲しさ」は $ 4 $ 増加します。 よって、 $ 1 $ 番目のケースに対する答えは、 $ 3+6+1+4=14 $ となります。 ### Constraints - 入力は全て整数 - $ 1 \le T \le 10^5 $ - $ 1 \le N \le 10^6 $ - $ 1 \le A,M \le 300 $