AT_past202209_i 毎日のリンゴ

Solve the following problem for $ T $ test cases. Takahashi has $ 10^{100} $ coupons, each worth $ M $ yen, available in Lunlun Mart. The shop does not give change on these coupons where the price of the purchased item is less than the value of the coupons. On the $ i $ -th day, Takahashi will buy an apple worth $ A \times i $ yen using only the coupons. Here, the *sadness* of Takahashi increases by $ k \times M - A \times i $ , where $ k $ is the minimum number of ( $ M $ -yen) coupons needed to pay at least $ A \times i $ yen. In $ N $ days of shopping, how much total sadness will Takahashi accumulate?

Input is given from Standard Input in the following format: > $ T $ $ \rm{case}_1 $ $ \rm{case}_2 $ $ \dots $ $ \rm{case}_T $ Here, $ \rm{case}_i $ represents the $ i $ -th test case in the following format: > $ N $ $ A $ $ M $

Print $ T $ lines. The $ i $ -th line should contain the answer to the $ i $ -th test case as an integer.

### Sample Explanation 1 This input contains $ 10 $ test cases. In the first case, $ N=4 $ , $ A=5 $ , and $ M=8 $ . - On the $ 1 $ -st day, he buys an apple worth $ 5 $ yen. One $ 8 $ -yen coupon is needed, and his sadness increases by $ 3 $ . - On the $ 2 $ -nd day, he buys an apple worth $ 10 $ yen. Two $ 8 $ -yen coupons are needed, and his sadness increases by $ 6 $ . - On the $ 3 $ -rd day, he buys an apple worth $ 15 $ yen. Two $ 8 $ -yen coupons are needed, and his sadness increases by $ 1 $ . - On the $ 4 $ -th day, he buys an apple worth $ 20 $ yen. Three $ 8 $ -yen coupons are needed, and his sadness increases by $ 4 $ . Therefore, the answer to this case is $ 3+6+1+4=14 $ . ### Constraints - All values in input are integers. - $ 1 \le T \le 10^5 $ - $ 1 \le N \le 10^6 $ - $ 1 \le A,M \le 300 $