# DIV + MOD solution codeforces

Not so long ago, Vlad came up with an interesting function:

• 𝑓𝑎(𝑥)=𝑥𝑎+𝑥mod𝑎fa(x)=⌊xa⌋+xmoda, where 𝑥𝑎⌊xa⌋ is 𝑥𝑎xa, rounded down𝑥mod𝑎xmoda — the remainder of the integer division of 𝑥x by 𝑎a.

For example, with 𝑎=3a=3 and 𝑥=11x=11, the value 𝑓3(11)=113+11mod3=3+2=5f3(11)=⌊113⌋+11mod3=3+2=5.

The number 𝑎a is fixed and known to Vlad. Help Vlad find the maximum value of 𝑓𝑎(𝑥)fa(x) if 𝑥x can take any integer value from 𝑙l to 𝑟r inclusive (𝑙𝑥𝑟l≤x≤r).

## DIV + MOD solution codeforces

The first line of input data contains an integer 𝑡t (1𝑡1041≤t≤104) — the number of input test cases.

This is followed by 𝑡t lines, each of which contains three integers 𝑙𝑖li𝑟𝑖ri and 𝑎𝑖ai (1𝑙𝑖𝑟𝑖109,1𝑎𝑖1091≤li≤ri≤109,1≤ai≤109) — the left and right boundaries of the segment and the fixed value of 𝑎a.

Output

For each test case, output one number on a separate line — the maximum value of the function on a given segment for a given 𝑎a.

Example
input

Copy
5
1 4 3
5 8 4
6 10 6
1 1000000000 1000000000
10 12 8


### DIV + MOD solution codeforces

2
4
5
999999999
5


## DIV + MOD solution codeforces

In the first sample:

• 𝑓3(1)=13+1mod3=0+1=1f3(1)=⌊13⌋+1mod3=0+1=1,
• 𝑓3(2)=23+2mod3=0+2=2f3(2)=⌊23⌋+2mod3=0+2=2,
• 𝑓3(3)=33+3mod3=1+0=1f3(3)=⌊33⌋+3mod3=1+0=1,
• 𝑓3(4)=43+4mod3=1+1=2f3(4)=⌊43⌋+4mod3=1+1=2

As an answer, obviously, 𝑓3(2)f3(2) and 𝑓3(4)f3(4) are suitable.