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

$f_a(x)=\left\lfloor\frac{x}{a}\right\rfloor + x mod a$, where $\left\lfloor\frac{x}{a}\right\rfloor$ is $\frac{x}{a}$, rounded down, $x mod a$ — the remainder of the integer division of $x$ by $a$.

For example, with $a=3$ and $x=11$, the value $f_3(11) = \left\lfloor\frac{11}{3}\right\rfloor + 11 mod 3 = 3 + 2 = 5$.

The number $a$ is fixed and known to Vlad. Help Vlad find the maximum value of $f_a(x)$ if $x$ can take any integer value from $l$ to $r$ inclusive ($l \le x \le r$).


-----Input-----

The first line of input data contains an integer $t$ ($1 \le t \le 10^4$) — the number of input test cases.

This is followed by $t$ lines, each of which contains three integers $l_i$, $r_i$ and $a_i$ ($1 \le l_i \le r_i \le 10^9, 1 \le a_i \le 10^9$) — 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$.


-----Examples-----

Input
5
1 4 3
5 8 4
6 10 6
1 1000000000 1000000000
10 12 8
Output
2
4
5
999999999
5


-----Note-----

In the first sample:

$f_3(1) = \left\lfloor\frac{1}{3}\right\rfloor + 1 mod 3 = 0 + 1 = 1$,

$f_3(2) = \left\lfloor\frac{2}{3}\right\rfloor + 2 mod 3 = 0 + 2 = 2$,

$f_3(3) = \left\lfloor\frac{3}{3}\right\rfloor + 3 mod 3 = 1 + 0 = 1$,

$f_3(4) = \left\lfloor\frac{4}{3}\right\rfloor + 4 mod 3 = 1 + 1 = 2$

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

Difficulty: EASY
Tags: Mathematics

Starter code:

Solutions:
lst = []
for _ in [*open(0)][1:]:
	(l, r, a) = map(int, _.split())
	print(max(r // a + r % a, (r - r % a - 1) // a + (r - r % a - 1) % a if r - r % a - 1 >= l else 0))


from sys import stdin
input = stdin.readline
for _ in range(int(input())):
	(l, r, a) = map(int, input().split())
	(ld, lm) = (l // a, l % a)
	(rd, rm) = (r // a, r % a)
	if ld < rd:
		ans = max(rd - 1 + a - 1, rd + rm)
	else:
		ans = rd + rm
	print(ans)


import sys
input = sys.stdin.readline
t = int(input())
for i in range(t):
	(l, r, a) = map(int, input().split())
	ans = r // a + r % a
	if l <= r // a * a - 1:
		ans1 = r // a - 1 + a - 1
		if ans1 > ans:
			ans = ans1
	print(ans)


import sys
import bisect
inp = sys.stdin.readline

def gcd(a, b):
	if b == 0:
		return a
	return gcd(b, a % b)

def lcm(a, b):
	return a * b // gcd(a, b)
for _ in range(int(inp())):
	(l, r, a) = map(int, inp().split())
	lm = r // a * a - 1
	ans = r // a + r % a
	if lm >= l:
		ans = max(ans, lm // a + lm % a)
	print(ans)


from math import floor
from sys import stdin
input = stdin.readline

def main():
	for _ in range(int(input())):
		(l, r, a) = map(int, input().split())
		rem = r % a
		if l // a == r // a:
			print(r // a + r % a)
		else:
			print(max(r // a + r % a, r // a + a - 2))
main()


for line in [*open(0)][1:]:
	(l, r, a) = map(int, line.split())
	print(max(r // a + r % a, (r - 1 - r % a) // a + (r - 1 - r % a) % a if r - 1 - r % a >= l else 0))


f = 0
results = []
n = int(input())
for i in range(n):
	(x, y, z) = map(int, input().split())
	if x // z == y // z:
		results.append(y // z + y % z)
	elif y % z < z - 1:
		f = max(y // z + y % z, y // z + z - 2)
		results.append(f)
	else:
		results.append(y // z + y % z)
for i in results:
	print(i)


import sys
t = int(sys.stdin.readline().strip())
for _ in range(t):
	(l, r, a) = list(map(int, sys.stdin.readline().split()))
	(lz, lm) = (l // a, l % a)
	(rz, rm) = (r // a, r % a)
	if lz == rz:
		print(max(lm, rm) + lz)
	else:
		print(max(rz - 1 + a - 1, rz + rm))


import sys
input = sys.stdin.readline

def inp():
	return int(input())

def inlt():
	return list(map(int, input().split()))

def main():
	test = inp()
	for _ in range(test):
		(left, right, a) = inlt()
		result = right // a + right % a
		if right % a < right - left:
			result = max(result, result - 1 - right % a + a - 1)
		print(result)
main()


ans = ''
num = int(input())
for i in range(num):
	(div_min, div_max, n) = map(int, input().split())
	if div_min > div_max - div_max % n - 1:
		ans += f'{div_max // n + div_max % n}\n'
	elif div_max // n + div_max % n > (div_max - div_max % n - 1) // n + (div_max - div_max % n - 1) % n:
		ans += f'{div_max // n + div_max % n}\n'
	else:
		ans += f'{(div_max - div_max % n - 1) // n + (div_max - div_max % n - 1) % n}\n'
print(ans)


t = int(input())
il = []
for i in range(0, t):
	(l, r, a) = map(int, input().split())
	if l <= r - r % a - 1:
		il.append(max(r // a + r % a, a - 1 + (r - r % a - 1) // a))
	else:
		il.append(max(r // a + r % a, l // a + l % a))
for x in il:
	print(x)


import sys
case = int(sys.stdin.readline())
for c in range(case):
	(start, end, num) = map(int, sys.stdin.readline().split())
	end_quotient = end // num
	target_num = end_quotient * num
	target_two_num = (end_quotient + 1) * num - 1
	if start < target_num and end != target_two_num:
		print(end // num - 1 + (num - 1))
	else:
		print(end // num + end % num)


def divmod(l, r, a):
	if l == r:
		x = r
		return x / a // 1 + x % a
	ost = r % a
	if ost == a - 1:
		x = r
		return x / a // 1 + x % a
	temp = r
	x = r - ost - 1
	if x / a // 1 + x % a > temp / a // 1 + temp % a and (x >= l and x <= r):
		return x / a // 1 + x % a
	else:
		return temp / a // 1 + temp % a
ans = []
n = int(input())
for i in range(n):
	(l, r, a) = map(int, input().split())
	ans.append(divmod(l, r, a))
for i in range(len(ans)):
	print(int(ans[i]))


from math import floor
t = int(input())
result = []
for i1 in range(t):
	in1 = input().split()
	(l, r, a) = (int(in1[0]), int(in1[1]), int(in1[2]))
	if a == 1:
		result.append(r)
	else:
		req_num = floor((r + 1) / a) * a - 1
		if req_num >= l:
			result.append(floor(req_num / a) + req_num % a)
		else:
			result.append(floor(r / a) + r % a)
for i2 in result:
	print(i2)


from sys import stdin
input = stdin.readline

def fa(x, a):
	return x // a + x % a
for _ in range(int(input())):
	(l, r, a) = map(int, input().split())
	print(max(fa(r, a), fa(max(r - r % a - 1, l), a)))


import sys
a = int(sys.stdin.readline())
for i in range(a):
	(p, q, r) = map(int, sys.stdin.readline().strip().split())
	temp = q // r * r - 1
	if temp < p:
		sys.stdout.write(str(q // r + q % r) + '\n')
	else:
		m = temp // r + temp % r
		m = max(m, q // r + q % r)
		sys.stdout.write(str(m) + '\n')


t = int(input())
result = []
for case in range(t):
	(l, r, a) = map(int, input().split())
	result.append(max(r // a + r % a, (r - r % a - 1) // a + (r - r % a - 1) % a if r - r % a - 1 >= l else 0))
for y in result:
	print(y)


k = []
for i in range(int(input())):
	(l, r, a) = map(int, input().split())
	max_value = r // a + r % a
	if l < r // a * a:
		prev_max_value = r // a - 1 + (a - 1)
	else:
		prev_max_value = max_value
	s = max(max_value, prev_max_value)
	k.append(s)
for t in k:
	print(t)


import sys
t = int(sys.stdin.readline())
for k in range(0, t):
	[l, r, a] = map(int, sys.stdin.readline().split())
	if int(l / a) == int(r / a):
		sys.stdout.write(str(int(r / a) + r % a) + '\n')
	else:
		f1 = int(l / a) + l % a
		f2 = int(r / a) + r % a
		f3 = int(r / a) + a - 2
		sys.stdout.write(str(max([f1, f2, f3])) + '\n')


nu = int(input())
m = [0 for i in range(nu)]
for i in range(nu):
	(l, r, a) = map(int, input().split())
	if l // a <= r // a - 1:
		m[i] = max(r // a - 1 + a - 1, r // a + r % a)
	else:
		m[i] = r // a + r % a
for i in m:
	print(i)


R = lambda : map(int, input().split())
L = lambda line: map(int, line.split())
for line in [*open(0)][1:]:
	(l, r, a) = L(line)
	x = r - 1 - r % a
	c2 = x // a + x % a if x >= l else 0
	print(max(r // a + r % a, c2))


import sys
input = sys.stdin.readline

def ii():
	return int(input())

def iit():
	return map(int, input().split())

def iil():
	return list(map(int, input().split()))

def si():
	return input()[:-1]

def solve():
	(l, r, a) = iit()
	f1 = l // a
	f2 = r // a
	ans = f2 + r % a
	if f1 < f2:
		ans = max(ans, f2 - 1 + a - 1)
	print(ans)
t = ii()
for i in range(t):
	solve()


import sys
input = sys.stdin.readline
output = []

def main():
	for _ in range(int(input())):
		(l, r, a) = map(int, input().split())
		if a == 1 or a > r:
			f = r
		elif r % a == 0:
			x = max(l, r - 1)
			f = x // a + x % a
		elif l < a < r:
			f = max(r // a + r % a, max(r // a - 1, l // a) + a - 1)
		elif a < l < r:
			(la, ra) = (l // a, r // a)
			f = max(ra + r % a, ra + a - 2 if la < ra else 0)
		else:
			f = max(map(lambda x: x // a + x % a, range(max(l, r - 1 - r % a), r + 1)))
		output.append(f)
	print(*output, sep='\n')
main()


def fn(i, j, a):
	f1 = j // a
	r1 = j % a
	f2 = 0
	r2 = 0
	if f1 * a - 1 >= i:
		f2 = f1 - 1
		r2 = a - 1
	return max(f1 + r1, f2 + r2)
a = int(input())
k = []
for i in range(a):
	b = input().split()
	b = [int(o) for o in b]
	k.append(fn(b[0], b[1], b[2]))
for g in k:
	print(g)


def f(x, a):
	res = x // a + x % a
	return res

def DIV_MOD(l, r, a):
	res = f(r, a)
	if l // a < r // a:
		if res > r // a - 1 + (a - 1):
			return res
		else:
			res = f(r // a * a - 1, a)
			return res
	else:
		return res
t = int(input())
final = []
for i in range(t):
	(l, r, a) = input().split()
	(l, r, a) = (int(l), int(r), int(a))
	res = DIV_MOD(l, r, a)
	final.append(res)
for i in final:
	print(i)


import sys

def input():
	return sys.stdin.readline().rstrip()
n = int(input())
for _ in range(n):
	(l, r, a) = map(int, input().split())
	if l == r:
		print(r // a + r % a)
	elif r % a == 0:
		print(max(r // a + r % a, (r - 1) // a + (r - 1) % a))
	else:
		k = r // a
		if k * a - 1 >= l:
			print(max(k - 1 + a - 1, k + r % a))
		else:
			print(max(k + r % a, l // a + l % a))


import sys
from math import sqrt, gcd, factorial
from collections import deque, Counter, OrderedDict
sys.setrecursionlimit(10 ** 6)
input = lambda : sys.stdin.readline()
I = lambda : int(input())
S = lambda : input().strip()
M = lambda : map(int, input().strip().split())
L = lambda : list(map(int, input().strip().split()))
mod = 1000000007
for _ in range(I()):
	(l, r, a) = M()
	if a == 1:
		print(r)
	elif l == r:
		print(r // a + r - r // a * a)
	elif r % a == a - 1:
		print(r // a + a - 1)
	elif r % a:
		if a * (r // a) - 1 >= l:
			print(r // a - 1 + a - 1)
		else:
			print(r // a + r - r // a * a)
	else:
		r -= 1
		print(r // a + r - r // a * a)


import sys
input = sys.stdin.readline
t = int(input())
for _ in range(t):
	(l, r, a) = map(int, input().split())
	n = r // a
	while a * n + (a - 1) <= r:
		n += 1
	if a * (n - 1) + (a - 1) > r:
		x = r
	elif a * (n - 1) + (a - 1) < l:
		x = r
	else:
		x = a * (n - 1) + (a - 1)
	print(x // a + x % a)


import sys
import math

def f(x):
	return x // a + x % a
for _ in range(int(sys.stdin.readline())):
	(l, r, a) = map(int, sys.stdin.readline().split())
	if a == 1:
		print(r)
	else:
		e = r % a
		if e == a - 1:
			x = r
			print(f(x))
		elif r // a > l // a:
			x = r // a * a - 1
			print(f(x))
		else:
			x = r
			print(f(x))


answer = ''

def func(x, a):
	return int(x / a) + x % a

def evalCase(l, r, a):
	l = int(l)
	r = int(r)
	a = int(a)
	x3 = a * int(r / a) - 1
	ans3 = func(x3, a)
	if x3 < l:
		ans3 = -1
	ans1 = func(r, a)
	ans2 = ans1
	if r - 1 >= l:
		ans2 = func(r - 1, a)
	ans = ans1
	if ans2 > ans:
		ans = ans2
	if ans3 > ans:
		ans = ans3
	return ans
numCases = int(input())
for i in range(numCases):
	answer += str(evalCase(*input().split(' '))) + '\n'
print(answer.strip('\n'))


import sys
input = sys.stdin.readline
print = sys.stdout.write

def main():
	g = int(input())
	for i in range(g):
		(a, b, c) = map(int, input().split())
		if b % c == 0:
			if c != 1:
				if b - 1 >= a:
					print(f'{b // c - 2 + c}\n')
				else:
					print(f'{b // c}\n')
			else:
				print(f'{b}\n')
		elif b // c - 2 + c > b // c + b % c and b // c * c - 1 >= a:
			print(f'{b // c - 2 + c}\n')
		else:
			print(f'{b // c + b % c}\n')
main()


import sys
TC = int(input())
for i in range(TC):
	(a, b, K) = list(map(int, sys.stdin.readline().split(' ')))
	aDiv = a // K
	aHold = a % K
	bDiv = b // K
	bHold = b % K
	if aDiv == bDiv:
		print(bDiv + bHold)
	else:
		print(max(bDiv - 1 + K - 1, bDiv + bHold))


itr = int(input())
op = [0] * itr
for i in range(itr):
	(l, r, a) = input().split()
	l = int(l)
	r = int(r)
	a = int(a)
	if int(l / a) == int(r / a):
		op[i] = int(r / a) + r % a
	else:
		op[i] = max(int(r / a) + r % a, int(r / a - 1) + a - 1)
print(*op, sep='\n')


from re import S
import sys

def div_mod():
	(l, r, a) = [int(x) for x in sys.stdin.readline().strip().split(' ')]
	lv = (l // a, l % a)
	rv = (r // a, r % a)
	if lv[0] < rv[0]:
		print(max([rv[0] + rv[1], rv[0] - 1 + a - 1]))
	else:
		print(rv[0] + rv[1])

def test():
	n = int(sys.stdin.readline().strip())
	for i in range(n):
		div_mod()
test()


from sys import stdin
input = stdin.readline
t = int(input())

def solve():
	(l, r, a) = map(int, input().split())
	div = r // a
	maxs = div * a - 1
	target = maxs
	if maxs < l or r == maxs + a:
		target = r
	res = target // a + target % a
	return res
for _ in range(t):
	print(solve())


from math import *
from sys import stdin, setrecursionlimit
from itertools import *
from collections import *
lines = stdin.readlines()
lines.reverse()
setrecursionlimit(10 ** 8)

def input():
	return lines.pop().strip('\n')
t = int(input())
while t:
	(l, r, a) = map(int, input().split())
	ans = r // a + r % a
	val = r - r % a
	val -= 1
	if val >= l and val <= r:
		ans = max(val // a + val % a, ans)
	print(ans)
	t -= 1


d = int(input())
lines = []
for x in range(d):
	line = input().split(' ')
	lines.append(line)
for line in lines:
	l = int(line[0])
	u = int(line[1])
	a = int(line[2])
	p = [u // a + u % a]
	if u // a - 1 >= l // a:
		p.append(u // a - 1 + a - 1)
	print(max(p))


from sys import stdin, stdout
from collections import defaultdict
input = stdin.readline
t = int(input().strip())
for _ in range(t):
	(l, r, a) = list(map(int, input().strip().split()))
	if r % a == a - 1:
		ans = a - 1 + r // a
		print(ans)
		continue
	rem = r % a
	x = r
	x = x - rem - 1
	if x >= l and x <= r:
		ans = x // a + x % a
	else:
		ans = r // a + r % a
	print(ans)


import sys
linesPerTest = 1
testArguments = []
i = 0
totalLines = 1
while i <= totalLines:
	line = sys.stdin.readline().rstrip('\n')
	if i == 0:
		totalLines = linesPerTest * int(line)
	else:
		testArguments.append(line)
	i += 1
testCases = []
for j in range(0, len(testArguments), linesPerTest):
	testCases.append(testArguments[j:j + linesPerTest])

def f(testArguments):
	args = testArguments[0].split()
	(l, r, a) = (int(args[0]), int(args[1]), int(args[2]))
	g = lambda x: x // a + x % a
	if r % a == a - 1:
		return g(r)
	x = r - (r % a + 1)
	if x >= l:
		return g(x)
	else:
		return g(r)
for testCase in testCases:
	print(f(testCase))


n = int(input(''))
l1 = []

def mod(l, r, a):
	max1 = int(r / a) + r % a
	s = r // a * a - 1
	if s >= l:
		max1 = max(max1, int(s / a) + s % a)
	return max1
for i in range(n):
	(l, r, a) = input().split()
	l = int(l)
	r = int(r)
	a = int(a)
	l1 += [mod(l, r, a)]
for k in l1:
	print(k)


import sys
from math import floor, inf

def inp():
	return sys.stdin.readline().strip()

def iinp():
	return int(inp())

def mp():
	return map(int, inp().split())

def liinp():
	return list(mp())

def solve(l, r, x):
	ans = r // x + r % x
	m = r // x * x - 1
	if m >= l:
		ans = max(ans, m // x + m % x)
	return ans
tc = iinp()
for _ in range(tc):
	(l, r, a) = liinp()
	print(solve(l, r, a))


n = int(input())
result = []
for _ in range(n):
	(a, b, x) = map(int, input().split())
	if a // x == b // x:
		result.append(b // x + b % x)
	else:
		result.append(max(b // x + b % x, b // x - 1 + x - 1))
for re in result:
	print(re)


import sys

def solve():
	inp = sys.stdin.readline
	(l, r, a) = map(int, inp().split())
	c = r // a + r % a
	x = (r // a - 1) * a + a - 1
	if x >= l and x <= r:
		c = max(c, x // a + x % a)
	print(c)

def main():
	for i in range(int(sys.stdin.readline())):
		solve()
main()


out = []
for _ in range(int(input())):
	(l, r, a) = map(int, input().split())
	x = r // a * a - 1
	if x >= l:
		out.append(max(x // a + x % a, r // a + r % a))
	else:
		out.append(r // a + r % a)
for i in out:
	print(i)


import sys, math
input = sys.stdin.readline
for _ in range(int(input())):
	(l, r, a) = map(int, input().split())
	s = max(sum(divmod(l, a)), sum(divmod(r, a)))
	g = (math.ceil(r / a) - 1) * a
	s = max(s, sum(divmod(g, a)))
	if g - 1 >= l:
		s = max(s, sum(divmod(g - 1, a)))
	if r - 1 >= l:
		s = max(s, sum(divmod(r - 1, a)))
	print(s)


t = int(input())
ans = [0] * t
for q in range(t):
	(l, r, a) = map(int, input().split())
	f = r // a + r % a
	x = r - r % a - 1
	if x >= l:
		if x // a + x % a > f:
			f = x // a + x % a
	ans[q] = f
for g in range(t):
	print(ans[g])


import sys
input = lambda : sys.stdin.readline().rstrip()
tc = int(input())
while tc:
	(l, r, a) = map(int, input().split())
	ans = r // a + r % a
	m = r // a * a - 1
	if m >= l and m <= r:
		ans = max(ans, m // a + m % a)
	print(ans)
	tc -= 1


import math
import sys
input = sys.stdin.readline

def inp():
	return int(input())

def invr():
	return map(int, input().split())
t = inp()
while t > 0:
	(l, r, a) = invr()
	x1 = math.floor(r / a) + r % a
	x2 = 0
	if r - r % a - 1 >= l:
		x2 = math.floor((r - r % a - 1) / a) + (r - r % a - 1) % a
	print(max(x1, x2))
	t -= 1


from operator import index
test_cases = int(input())

def checker(left, right, a):
	highest_input = right - right % a - 1
	true_first = int(right / a) + right % a
	if highest_input >= left and highest_input <= right:
		first = int(highest_input / a) + highest_input % a
		if highest_input - a >= left and highest_input - a <= right:
			second = int((highest_input - a) / a) + (highest_input - a) % a
			return max((first, second, true_first))
		else:
			return max((first, true_first))
	else:
		return true_first
answers = []
for test_case in range(test_cases):
	(left, right, a) = [int(i) for i in input().split()]
	answers.append(checker(left, right, a))
for ans in answers:
	print(ans)


import math
n_test_cases = int(input())
results = []
for _ in range(n_test_cases):
	(l, r, a) = tuple([int(x) for x in input().split()])
	values = []
	values.append(r % a + math.floor(r / a))
	if r - 1 >= l:
		r2 = r - 1
		values.append(r2 % a + math.floor(r2 / a))
	if r - r % a - 1 >= l:
		r3 = r - r % a - 1
		values.append(r3 % a + math.floor(r3 / a))
	results.append(max(values))
for result in results:
	print(result)


import math
tcase = int(input())
final = []
for i in range(0, tcase):
	(l, r, a) = map(int, input().split())
	c1 = a * math.ceil(r / a) - 1
	c2 = a * math.floor(r / a) - 1
	if a == 1:
		final.append(r)
	elif c1 <= r and c1 >= l:
		final.append(int((c1 + 1) / a - 1 + c1 % a))
	elif c2 <= r and c2 >= l:
		final.append(int((c2 + 1) / a - 1 + c2 % a))
	else:
		final.append(math.floor(r / a) + r % a)
for i in final:
	print(i)


from posixpath import split
m = 0
t = int(input())
s = []
for i in range(t):
	s.append(input())
for i in range(t):
	max = 0
	l = s[i].split(' ')
	l0 = int(l[0])
	l1 = int(l[1])
	l2 = int(l[2])
	if l2 == 1:
		print(l1)
		continue
	if l1 % l2 == l2 - 1:
		pass
	elif l1 // l2 >= 1:
		m = l1
		l1 -= l1 % l2 + 1
		if l1 < l0:
			l1 = m
	l1 = l1 // l2 + l1 % l2
	print(l1)


cases = []
for i in range(int(input())):
	cases.append([int(i) for i in input().split()])
for case in cases:
	a = case[2]
	first = case[1] // a + case[1] % a
	x = case[1] - case[1] % a - 1
	if x < case[0]:
		print(first)
	else:
		print(max(x // a + x % a, first))


import math
import sys
import itertools
import fractions
wtf = sys.stdin.read()
wtf = wtf.strip().split('\n')
t = int(wtf[0])
for s in wtf[1:]:
	(l, r, a) = map(int, s.split())
	ans = r // a + r % a
	m = r // a * a - 1
	if m >= l:
		ans = max(ans, m // a + m % a)
	print(ans)


import math

def f(a, x):
	return math.floor(x / a) + x % a
t = int(input())
li = []
for _ in range(t):
	li += [list(map(int, input().split()))]
for i in range(t):
	l = li[i][0]
	r = li[i][1]
	a = li[i][2]
	if r % a == a - 1:
		print(f(a, r))
	elif r - r % a - 1 >= l:
		print(f(a, r - r % a - 1))
	else:
		print(f(a, r))


import math
loops = int(input())
equation = []
for i in range(loops):
	inp = input().split()
	l = int(inp[0])
	r = int(inp[1])
	a = int(inp[2])
	test = 0
	if r == a:
		if r != l:
			equation.append((a - 1) % a)
		else:
			equation.append(int(l / a))
	elif r == 1 or l == r:
		equation.append(int(l / a + l % a))
	elif a == 1:
		equation.append(int(r / a))
	else:
		diff = r - r % a - 1
		if l <= diff:
			floor = math.floor(diff / a)
			floorR = math.floor(r / a)
			if int(r / a + r % a) > int(diff / a + diff % a):
				equation.append(floorR + r % a)
			else:
				equation.append(floor + diff % a)
		else:
			equation.append(int(r / a + r % a))
for i in equation:
	print(i)


class Solution:

	def divPlusMod(self, arr):
		ans = first = secod = 0
		(l, r, a) = (arr[0], arr[1], arr[2])
		newa = a if a > l else l + a - (l + a) % a
		if l == r:
			return l // a + l % a
		if a == 1:
			return r
		if a >= r:
			return r % a if a > r else (r - 1) % a
		elif l < a < r:
			ans = (a - 1) // a + (a - 1) % a
		newa = r - r % a
		c = (newa - 1) // a + (newa - 1) % a
		if newa - 1 >= l:
			ans = max(ans, c)
		temp = r // a + r % a if r % a or r == a else (r - 1) // a + (r - 1) % a
		ans = max(ans, temp)
		return ans
obj = Solution()
ta = []
tc = int(input())
for i in range(tc):
	arr = list(map(int, input().strip().split()))[:3]
	ta.append(obj.divPlusMod(arr))
for i in ta:
	print(i)


def find(l, r, a):
	b = r // a
	v = a * b - 1
	if (r + 1) % a == 0:
		return r // a + r % a
	elif v >= l:
		return v // a + v % a
	else:
		return r // a + r % a
t = int(input())
ll = []
lr = []
la = []
for i in range(t):
	(l, r, a) = map(int, input().split())
	ll.append(l)
	lr.append(r)
	la.append(a)
for i in range(t):
	print(find(ll[i], lr[i], la[i]))


def compute(l, r, a):
	z = r % a
	k = r - z - 1
	if k < l or z == a - 1:
		k = r
	return k // a + k % a
t = int(input())
for _ in range(t):
	(l, r, a) = map(int, input().split())
	print(compute(l, r, a))


import math
t = int(input())
for k in range(t):
	s = input().split()
	l = int(s[0])
	r = int(s[1])
	a = int(s[2])
	if r % a < a - 2:
		b = r // a - 1
		if r - r % a - 1 < l:
			print(r // a + r % a)
			continue
		print(b + a - 1)
	else:
		print(r // a + r % a)


t = int(input())
for _ in range(t):
	(l, r, a) = map(int, input().split())
	if a == 1:
		print(r)
	else:
		m = r % a
		if m == a - 1:
			print(r // a + m)
		elif r - m - 1 >= l:
			print((r - m - 1) // a + a - 1)
		else:
			print(r // a + m)


t = int(input())
for i in range(t):
	(l, r, a) = list(map(int, input().split()))
	print(max((r - (r % a + 1)) // a + (r - (r % a + 1)) % a if r - (r % a + 1) >= l else -1000, r // a + r % a))


for _ in range(int(input())):
	(l, r, a) = map(int, input().split())
	temp = r // a * a
	if r % a == a - 1:
		print(r // a + r % a)
	elif temp - 1 >= l:
		print(temp // a + a - 2)
	else:
		print(r // a + r % a)


n = int(input())
for i in range(n):
	(l, r, a) = [int(i) for i in input().split()]
	if r // a * a + (a - 1) == r:
		print(r // a + (a - 1))
	elif (r // a - 1) * a + (a - 1) >= l:
		print(r // a + (a - 1) - 1)
	else:
		print(r // a + r % a)


def solve():
	(l, r, a) = [int(x) for x in input().split()]
	ans = r - (r % a + 1) % a
	if ans < l:
		ans = r
	return ans // a + ans % a
for tc in range(int(input())):
	print(solve())