B. DIV + MOD

time limit per test

2 seconds

memory limit per test

256 megabytes

input

standard input

output

standard output

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

• fa(x)=⌊xa⌋+xmodafa(x)=⌊xa⌋+xmoda, where ⌊xa⌋⌊xa⌋ is xaxa, rounded down, xmodaxmoda — the remainder of the integer division of xx by aa.

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

The number aa is fixed and known to Vlad. Help Vlad find the maximum value of fa(x)fa(x) if xx can take any integer value from ll to rr inclusive (l≤x≤rl≤x≤r).

Input

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

This is followed by tt lines, each of which contains three integers lili, riri and aiai (1≤li≤ri≤109,1≤ai≤1091≤li≤ri≤109,1≤ai≤109) — the left and right boundaries of the segment and the fixed value of aa.

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 aa.

Example

input

Copy

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

output

Copy

2
4
5
999999999
5

Note

In the first sample:

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

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

解题说明：此题是一道数学题，找规律求解即可。

#include
 
int main()
{
	int t, l, r, i, sum;
	scanf("%d", &t);
	while (t--) 
	{
		scanf("%d%d%d", &l, &r, &i);
		if (l / i == r / i || (r + 1) % i == 0) 
		{
			sum = r / i + r % i;
		}
		else
		{
			sum = (r / i - 1) + i - 1;
		}
		printf("%d\n", sum);
	}
	return 0;
}