Read problems statements in [Hindi], [Mandarin Chinese], [Russian], [Vietnamese] and [Bengali] as well.

Misha calls a non-empty set of positive integers *nice* if it has the following properties:
Each element of the set is between $l$ and $r$ (inclusive).
The greatest positive integer which divides each element of the set is exactly $g$.

Misha likes nice sets, so she wants to find the size of the largest nice set. Help her solve the problem.

------  Input ------
The first line of the input contains a single integer $T$ denoting the number of test cases. The description of $T$ test cases follows.
The first and only line of each test case contains three space-separated integers $l$, $r$ and $g$.

------  Output ------
For each test case, print a single line containing one integer — the maximum number of elements in a nice set, or $0$ if no nice set exists.

------  Constraints  ------
$1 ≤ T ≤ 200$
$1 ≤ g ≤ 10^{18}$
$1 ≤ l ≤ r ≤ 10^{18}$

----- Sample Input 1 ------ 
2

5 15 4

15 20 35
----- Sample Output 1 ------ 
2

0
----- explanation 1 ------ 
Example case 1: Misha can choose the set $\{8, 12\}$.

Example case 2: All numbers in the range $[l, r]$ are smaller than $35$, so there is no way to choose a non-empty subset of these numbers where each element is divisible by $35$ and the answer is $0$.

Difficulty: MEDIUM_HARD
Tags: Number theory

Mathematics

Starter code:

Solutions:
t = int(input())
for i in range(t):
	(l, r, g) = input().split()
	l = int(l)
	r = int(r)
	g = int(g)
	c = r // g - (l - 1) // g
	if c == 1:
		if l > g or g > r:
			print(0)
		else:
			print(c)
	else:
		print(c)


import math
t = int(input())
for _ in range(t):
	(l, r, g) = map(int, input().split())
	quo = r // g - (l - 1) // g
	if quo == 1:
		if l > g or g > r:
			print(0)
		else:
			print(quo)
	else:
		print(quo)


T = int(input())
for _ in range(T):
	(l, r, q) = map(int, input().split())
	n = r // q - (l - 1) // q
	if n == 1:
		if not (l <= q and q <= r):
			print(0)
		else:
			print(n)
	else:
		print(n)


T = int(input())
for i in range(T):
	(l, r, g) = map(int, input().split())
	c = r // g - (l - 1) // g
	print(0 if c == 1 and g < l else c)


def answer():
	ans = r // g - l // g + (l % g == 0)
	if ans != 1:
		return ans
	else:
		if l <= g and r >= g:
			return 1
		return 0
for T in range(int(input())):
	(l, r, g) = map(int, input().split())
	print(answer())


t = int(input())
for you in range(t):
	l = input().split()
	L = int(l[0])
	R = int(l[1])
	g = int(l[2])
	num = R // g - (L - 1) // g
	if num > 1:
		print(num)
	elif num == 1:
		if L <= g and g <= R:
			print(1)
		else:
			print(0)
	else:
		print(0)


import math
for _ in range(int(input())):
	(l, r, g) = map(int, input().split())
	left = (l - 1) // g
	right = r // g
	if right - left == 1:
		if l <= g and g <= r:
			print(right - left)
		else:
			print(0)
	else:
		print(right - left)


for _ in range(int(input())):
	(l, r, g) = map(int, input().split())
	x = (l - 1) // g
	y = r // g
	s = y - x
	f = 1
	if s == 1:
		if g < l or g > r:
			f = 0
	if f == 1:
		print(s)
	else:
		print(0)


for u in range(int(input())):
	(l, r, g) = map(int, input().split())
	x = (l - 1) // g
	y = r // g
	s = y - x
	f = 1
	if s == 1:
		if g >= l and g <= r:
			f = 1
		else:
			f = 0
	if f:
		print(s)
	else:
		print(0)


for _ in range(int(input())):
	(l, r, g) = [int(x) for x in input().split()]
	cnt1 = l // g
	cnt2 = r // g
	if l % g == 0:
		x = cnt2 - cnt1 + 1
		if x == 1 and (g < l or g > r):
			print(0)
		else:
			print(x)
	else:
		x = cnt2 - cnt1
		if x == 1 and (g < l or g > r):
			print(0)
		else:
			print(x)


for _ in range(int(input())):
	(l, r, g) = map(int, input().split())
	x = (l - 1) // g
	y = r // g
	k = y - x
	flag = 1
	if k == 1:
		if g >= l and r >= g:
			flag = 1
		else:
			flag = 0
	if flag:
		print(k)
	else:
		print(0)


for _ in range(int(input())):
	(l, r, g) = map(int, input().split())
	start = (l - 1) // g
	end = r // g
	p = end - start
	if p == 1:
		if g >= l and r >= g:
			p = 1
		else:
			p = 0
	p1 = max(p, 0)
	print(p1)


for _ in range(int(input())):
	(l, r, g) = map(int, input().split())
	if g > r:
		print(0)
	else:
		t_1 = r // g
		t_2 = (l - 1) // g
		if t_1 - t_2 == 1:
			if g >= l and g <= r:
				print(1)
			else:
				print(0)
		else:
			print(t_1 - t_2)


t = int(input())
for num in range(t):
	(l, r, g) = input().strip().split(' ')
	(l, r, g) = [int(l), int(r), int(g)]
	if g > r:
		print(0)
	else:
		total = r // g - (l - 1) // g
		if total == 1 and g < l:
			total = 0
		print(total)


t = int(input())
import math
while t > 0:
	(l, r, g) = map(int, input().split())
	x = l // g
	y = r // g
	c = y - x
	if l % g == 0:
		c += 1
	if c < 1:
		print(0)
	elif c == 1:
		if g <= r and g >= l:
			print(1)
		else:
			print(0)
	else:
		print(c)
	t -= 1


import math
t = int(input())
for _ in range(t):
	(l, r, g) = list(map(int, input().strip().split()))
	count = r // g - l // g
	if l % g == 0:
		count += 1
	if count == 0:
		print(0)
	elif count == 1:
		if g >= l and g <= r:
			print(count)
		else:
			print(0)
	else:
		print(count)


for _ in range(int(input())):
	(l, r, g) = map(int, input().split())
	le = (l - 1) // g
	re = r // g
	res = re - le
	if res == 1 and g < l:
		res = 0
	print(res)


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


t = int(input())
for _ in range(t):
	(l, r, g) = map(int, input().split())
	suk = l // g
	hak = r // g
	if l % g == 0:
		leng = hak - suk + 1
	else:
		leng = hak - suk
	if leng == 1:
		if l <= g:
			print(1)
		else:
			print(0)
	else:
		print(leng)


t = int(input())
while t:
	t -= 1
	(l, r, g) = [int(i) for i in input().split()]
	count = r // g - l // g
	if l % g == 0:
		count += 1
	if count == 1:
		if g >= l and g <= r:
			print(1)
		else:
			print(0)
	else:
		print(count)


t = int(input())
while t:
	t -= 1
	(l, r, g) = [int(i) for i in input().split()]
	count = 0
	a = []
	if r < g:
		print(0)
	else:
		if l <= g:
			i = g
		elif l % g == 0:
			i = l
		else:
			i = g - l % g
			i = l + i
		if i <= r:
			a.append(i)
		if len(a) == 0:
			print(0)
		else:
			i = r % g
			j = r - i
			if j == a[0]:
				if a[0] == g:
					print(1)
				else:
					print(0)
			else:
				a.append(j)
				count = (a[1] - a[0]) // g
				print(count + 1)


t = int(input())
while t != 0:
	(l, r, g) = map(int, input().split())
	d = r // g - (l - 1) // g
	if d != 1:
		print(d)
	elif l <= g and g <= r:
		print(1)
	else:
		print(0)
	t -= 1


import math
T = int(input())
for t in range(T):
	(l, r, g) = [int(i) for i in input().split()]
	start_val = (l - 1) // g
	end_val = r // g
	length = end_val - start_val
	if length == 1:
		if g >= l and r >= g:
			length = 1
		else:
			length = 0
	print(max(length, 0))


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


def solve(l, r, g):
	ans = r // g - l // g
	if l % g == 0:
		ans += 1
	if ans == 1:
		if g >= l and g <= r:
			print(ans)
		else:
			print(0)
	else:
		print(ans)
for t in range(int(input())):
	(l, r, g) = list(map(int, input().split()))
	solve(l, r, g)


for _ in range(int(input())):
	(l, r, g) = map(int, input().split())
	max1 = r // g
	min1 = l // g
	if l % g == 0:
		min1 -= 1
	ans = max1 - min1
	if ans == 1:
		if l <= g and r >= g:
			print(1)
		else:
			print(0)
	else:
		print(ans)


t = int(input())
for _ in range(t):
	(l1, r1, g) = [int(i) for i in input().split()]
	l = (l1 - 1) // g
	r = r1 // g
	if r - l == 1 and (not l1 <= g <= r1):
		print(0)
	else:
		print(r - l)


test = int(input())
for iteration in range(test):
	(l, r, g) = [int(i) for i in input().split()]
	cnt = r // g - (l - 1) // g
	if cnt == 1:
		if g >= l:
			print(cnt)
		else:
			print(0)
	else:
		print(cnt)


import sys
from math import ceil, floor
RI = lambda : [int(x) for x in sys.stdin.readline().split()]
rw = lambda : sys.stdin.readline().strip()
for _ in range(int(input())):
	(a, b, c) = RI()
	l = (a - 1) // c
	r = b // c
	if r - l == 1 and (not a <= c <= b):
		print(0)
	else:
		print(r - l)


for i in range(int(input())):
	(l, r, g) = map(int, input().split())
	n = r // g - (l - 1) // g
	if n == 1:
		if g >= l:
			print(1)
		else:
			print(0)
	else:
		print(n)


t = int(input())
for _ in range(t):
	(n, m, k) = map(int, input().split())
	val1 = (n - 1) // k
	val2 = m // k
	res = val2 - val1
	if res != 1:
		print(res)
	elif n <= k and m >= k:
		print(1)
	else:
		print(0)


t = int(input())
for i in range(t):
	(l, r, g) = map(int, input().split())
	a = (l - 1) // g
	b = r // g
	if b - a != 1:
		print(b - a)
	elif l <= g and r >= g:
		print(1)
	else:
		print(0)


for i in range(int(input())):
	(l, r, g) = map(int, input().split())
	k = (l - 1) // g
	m = r // g
	c = m - k
	if c != 1:
		print(c)
	elif l <= g and r >= g:
		print(1)
	else:
		print(0)


T = int(input())
for z in range(T):
	(L, R, G) = map(int, input().split())
	mx = R // G
	mn = L // G
	if L % G == 0:
		mn -= 1
	ans = mx - mn
	if ans == 1:
		if G >= L and G <= R:
			print(1)
		else:
			print(0)
	else:
		print(ans)


from collections import defaultdict as dd
from collections import Counter as ccd
from itertools import permutations as pp
from itertools import combinations as cc
from random import randint as rd
from bisect import bisect_left as bl
from bisect import bisect_right as br
import heapq as hq
from math import gcd
mod = pow(10, 9) + 7

def inp(flag=0):
	if flag == 0:
		return list(map(int, input().strip().split(' ')))
	else:
		return int(input())
t = inp(1)
while t:
	t -= 1
	(l, r, g) = inp()
	l = l + (g - l % g) % g
	r = r - r % g
	if r < l:
		print(0)
	elif l == r:
		if l != g:
			print(0)
		else:
			print(1)
	else:
		print(r // g - l // g + 1)


import math
t = int(input())
while t:
	(l, r, e) = [int(x) for x in input().split()]
	if e > r:
		print(0)
	else:
		ans = r // e - l // e
		if l % e == 0:
			ans += 1
		if ans != 1:
			print(ans)
		elif l <= e:
			print(1)
		else:
			print(0)
	t -= 1


t = int(input())
for _ in range(t):
	(l, r, g) = map(int, input().split())
	if l % g == 0:
		n1 = l // g
	else:
		n1 = l // g + 1
	n2 = r // g
	if n2 - n1 != 0:
		print(n2 - n1 + 1)
	elif n1 == 1:
		print(1)
	else:
		print(0)


n = lambda : map(int, input().split())
x = int(input())
for __ in range(x):
	(a, b, c) = n()
	i = a // c
	j = b // c
	if a % c == 0:
		j += 1
	if j - i == 1:
		if a > c or b < c:
			j = i
	print(j - i)


t = int(input())
while t:
	t = t - 1
	(l, r, g) = map(int, input().split())
	x1 = l % g
	if x1 == 0:
		b1 = l // g
	else:
		x = g - x1
		b1 = (l + x) // g
	x = r % g
	b2 = (r - x) // g
	temp = b2 - b1 + 1
	if temp == 1 and b2 != 1:
		print('0')
	else:
		print(b2 - b1 + 1)


for _ in range(int(input())):
	(l, r, g) = map(int, input().split())
	d = r // g - (l - 1) // g
	if d != 1:
		print(d)
	elif l <= g and g <= r:
		print(1)
	else:
		print(0)


t = int(input())
while t > 0:
	(l, r, g) = input().split(' ')
	l = int(l)
	r = int(r)
	g = int(g)
	if l % g == 0:
		left = l
	else:
		left = g * (l // g + 1)
	if r % g == 0:
		right = r
	else:
		right = g * (r // g)
	amount = right // g - left // g + 1
	if g > r:
		print('0')
	elif amount <= 1:
		if left == g:
			print(amount)
		else:
			print('0')
	else:
		print(amount)
	t -= 1


t = int(input())
for i in range(t):
	(l, r, g) = map(int, input().split(' '))
	if r < l:
		print(0)
	else:
		start = l + (g - l % g) % g
		end = r - r % g
		if start > end:
			print(0)
		else:
			ans = (end - start) // g + 1
			if ans == 1 and end != g:
				ans = 0
			if ans < 0:
				ans = 0
			print(ans)


T = int(input())
for j in range(T):
	(l, r, g) = map(int, input().split(' '))
	a = l // g
	b = l / g
	if l % g != 0:
		a = a + 1
	st = g * a
	c = r // g
	en = g * c
	o = (en - st) // g + 1
	if r < g or st > en:
		o = 0
	if o == 1:
		if en != g:
			o = 0
	elif o <= 0:
		o = 0
	print(o)


for _ in range(int(input())):
	ans = 0
	(l, r, g) = [int(a) for a in input().split()]
	if r < g:
		ans = 0
	else:
		a1 = (g - l % g) % g + l
		l1 = r - r % g
		ans = (l1 - a1) // g + 1
	if ans < 0:
		ans = 0
	elif ans == 1 and l1 != g:
		ans = 0
	print(ans)


def _gcdset_algo(l, r, g):
	if l % g == 0:
		count = r // g - l // g + 1
	else:
		count = r // g - l // g
	if count == 1:
		if l <= g and g <= r:
			return 1
		else:
			return 0
	return count
test_cases = int(input())
for _ in range(test_cases):
	lrg_str = input().split()
	l = int(lrg_str[0])
	r = int(lrg_str[1])
	g = int(lrg_str[2])
	val = _gcdset_algo(l, r, g)
	print(val)


t = int(input())
import math

def meth(A, B, M):
	if A % M == 0:
		return B // M - A // M + 1
	return B // M - A // M
for i in range(t):
	(l, r, g) = list(map(int, input().split()))
	a = meth(l, r, g)
	if a == 1 and g < l:
		a = 0
	print(a)


t = int(input())
while t > 0:
	arr = list(map(int, input().split()))
	l = arr[0]
	r = arr[1]
	g = arr[2]
	if g <= 0:
		print(0)
	elif l % g == 0:
		b = abs(r // g - l // g)
		c = b + 1
		if c == 1:
			if l == g:
				print(c)
			else:
				print(0)
		else:
			print(c)
	else:
		c = abs(r // g - l // g)
		if c == 1:
			if g == (l // g + 1) * g:
				print(c)
			else:
				print(0)
		else:
			print(c)
	t -= 1


def solve():
	(l, r, g) = [int(x) for x in input().strip().split()]
	if l % g == 0:
		start = l // g
	else:
		start = l // g + 1
	end = r // g
	cnt = max(0, end - start + 1)
	if cnt == 1:
		if g < l or r < g:
			cnt = 0
	print(cnt)

def main():
	t = int(input())
	while t > 0:
		solve()
		t -= 1
main()


t = int(input())
ans = list()
while t > 0:
	(l, r, g) = [int(num) for num in input().split()]
	temp = r // g - l // g
	if l % g == 0:
		temp += 1
	if temp == 1 and (not (l <= g and g <= r)):
		temp = 0
	ans.append(temp)
	t = t - 1
for y in ans:
	print(int(y))


t = int(input())
while t > 0:
	(l, r, g) = map(int, input().split(' '))
	anw = r // g - (l - 1) // g
	if anw == 1:
		if r // g == 1:
			print(1)
		else:
			print(0)
	else:
		print(anw)
	t = t - 1


for _ in range(int(input())):
	[l, r, g] = list(map(int, input().split()))
	left = (l - 1) // g
	right = r // g
	res = right - left
	if res == 1:
		if l <= g and r >= g:
			print(res)
		else:
			print(0)
	else:
		print(res)


for _ in range(int(input())):
	(l, r, g) = map(int, input().split())
	temp1 = (l - 1) // g
	temp2 = r // g
	if temp2 - temp1 == 1 and temp2 > 1:
		print(temp2 - temp1 - 1)
	else:
		print(temp2 - temp1)


for t in range(int(input())):
	(l, r, g) = map(int, input().split())
	cnt = r // g - l // g
	if l % g == 0:
		cnt = cnt + 1
	if cnt == 1 and l > g:
		cnt = 0
	print(cnt)


t = int(input())
for w in range(t):
	(l, r, g) = map(int, input().split())
	if l != r:
		if l % g == 0:
			li = l // g
		else:
			li = l // g + 1
		ri = r // g
		if ri == 0:
			print(0)
		elif ri - li + 1 == 1:
			if g * li == g:
				print(1)
			else:
				print(0)
		else:
			print(ri - li + 1)
	elif l == g:
		print(1)
	else:
		print(0)


for _ in range(int(input())):
	(l, r, g) = map(int, input().split())
	p1 = r // g
	p2 = l // g
	answer = p1 - p2
	if l % g == 0:
		answer = answer + 1
	if l > g and answer == 1:
		answer = 0
	print(answer)


for _ in range(int(input())):
	(l, r, g) = map(int, input().split(' '))
	(i, j, ans) = (0, 0, 0)
	if g > l and g > r:
		print(0)
	else:
		j = r // g
		if l < g:
			print(j)
		else:
			i = l // g if l % g == 0 else l // g + 1
			ans = j - i + 1
			if ans == 1 and l > g:
				print(0)
			else:
				print(ans)


n = int(input())
for i in range(0, n):
	p = input().rstrip().split(' ')
	T = p[0:2]
	T.sort(key=int)
	l = int(T[0])
	r = int(T[1])
	g = int(p[2])
	A = r // g
	B = (l - 1) // g
	if g < l and A - B == 1:
		print(0)
	else:
		print(A - B)


t = int(input())
while t > 0:
	t -= 1
	(l, r, g) = [int(x) for x in input().split()]
	ans = r // g - l // g
	if l % g == 0:
		ans += 1
	if ans == 1 and l > g:
		ans = 0
	print(ans)


for _ in range(int(input())):
	(l, r, g) = list(map(int, input().strip().split()))
	ans = r // g - l // g
	if l % g == 0:
		ans += 1
	if ans == 1 and (g > r or g < l):
		print(0)
	else:
		print(ans)


t = int(input())
for z in range(t):
	(l, r, g) = map(int, input().split())
	ct = r // g - l // g
	if l % g == 0:
		ct += 1
	if l > r:
		ct = 0
	if l > g and ct == 1:
		ct = 0
	print(ct)


for t in range(int(input())):
	(l, r, g) = map(int, input().split())
	s = r // g
	if l % g == 0:
		se = l // g
	else:
		se = l // g + 1
	d = s - se + 1
	if d > 1 or (l <= g and r >= g):
		print(d)
	else:
		print(0)