Today is your birthday. You have decided to give away candies to your friends.

You have NN friends and MM candies. Suppose the 1st1st friend has LL buckets, 2nd2nd has L+1L+1 buckets, 3rd3rd has L+2L+2 buckets, and so on — in general, the ithith friend has L+i−1L+i−1 buckets.

## Buckets Full of Candies codechef solution

You start distributing candies from the NthNth friend and go towards the 1st1st friend.

For each friend, you put the **maximum** number of candies in each bucket such that all the buckets for that friend have an equal number of candies in them. Now, you take the remaining candies, move to the next friend, and repeat the above step.

Find the number of candies which will remain with you after visiting all your friends.

### Input Format

- The first line of input will contain a single integer TT, the number of test cases. Then the test cases follow.
- Each test case consists of a single line of input, containing three space-separated integers N,M,LN,M,L — representing the number of friends, number of candies that you have, and the number of buckets with the 1st1st friend respectively.

### Output Format

For each test case, output a single integer representing the total number of candies left with you after distributing candies to all your friends.

## Buckets Full of Candies codechef solution

- 1≤T≤1051≤T≤105
- 0≤N,M≤10180≤N,M≤1018
- 1≤L≤10181≤L≤1018

### Sample Input 1

```
4
2 8 2
3 9 2
3 10 2
4 100 10
```

### Sample Output 1

```
0
1
0
9
```

## Buckets Full of Candies codechef solution

**Test case 11:** There are two friends. The 1st1st friend has 22 buckets and the 2nd2nd friend has 33 buckets. You will give 66 candies to 2nd2nd friend (22 in each bucket). Now you are left with 22 candies, which you will give to the 1st1st friend (11 in each bucket). You will be left with 00 candies at the end.

**Test case 22:** There are 33 friends and 99 candies. The 1st1st friend has 22 buckets, 2nd2nd friend has 33 buckets, and 3rd3rd friend has 44 buckets. You will give 88 candies to the 3rd3rd friend (22 in each bucket). Now the 2nd2nd friend and 1st1st friend will get 00 candies. You will be left with 11 candy at the end.

**Test case 33:** There are 33 friends and 1010 candies. You will give 88 candies to the 3rd3rd friend (22 in each bucket). Next, the 2nd2nd friend will get 00 candies. Finally, the 1st1st friend will get 22 candies (11 in each bucket). You will be left with 00 candies at the end.