Lui is in Dhaka head office now. You all know Lui, a mosquito and a TV celebrity. He is trying to spread dengue fever all over Bangladesh, specially in Dhaka. He and his team are trying hard to fulfill their mission. We are seeing that he is successfully spreading dengue and people are getting infected by dengue virus everyday. Now being a concerned citizen, we should take steps to prevent dengue. For that, we need to eradicate Aedes mosquito. As a first step, we can achieve the goal by listing the number of Aedes mosquitoes that is increasing every day. Some volunteers have already started to collect data about the increasing rate of mosquitoes. But if we could find the total number of mosquitoes up to a given future date, it will be easier to decrease mosquitoes and save people. For that reason, we need your help. You will be given some data and you will have to calculate the sum of readings that were taken by the volunteers from the first day to a particular day.

You will be given the number of Aedes mosquitoes on the first day and the common difference of the quantity of mosquitoes between the two consecutive days. It is guaranteed that, the number of mosquitoes will be strictly increasing every day.

Input

First line of the input contains an integer $T$ ($1 \le T \le 1000$) which denotes the number of test cases. Then for each test case there will be a integer $Q$ ($1 \le Q \le 500$) which denotes number of query we want to make. Then for each query, there will be three positive integers $a$, $d$, $n$ ($0 ≤ a, d, n ≤ 10^5$) that denotes number of Aedes mosquito on the first day, common difference of the number of mosquito between the two subsequent days and the nth day till which we want to calculate the sum of mosquitoes.

Output

For each input, output the sum of the readings of mosquitoes from the first to the $n$-th day.

Sample

Input

Output

2
2
1 2 7
4 2 9
1
0 3 7

49
108
63

In the first sample, we had a single mosquito in the first day. Then next six days will have 3, 5, 7, 9, 11 and 13 mosquitoes respectively. So the summation is 49.