Read problem statements in [Mandarin], [Bengali], [Russian], and [Vietnamese] as well.

Ujan is a software developer. He is developing a software that takes two integers L and R and outputs the count of integers in the sequence L,L+1,\ldots,R-1,R whose sum of digits (SOD) is divisible by 3. 

He has developed the user interface (UI) quite easily. He is having a hard time finding the logic to solve the problem. As you are not only a good friend of Ujan but also a good problem solver, he asks you to help him out.

Can you solve the problem for your friend, Ujan? 

------ Input Format ------ 

- 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 only line of each test case contains two integer L,R. 

------ Output Format ------ 

For each test case, print a single line containing one integer equal to the count of of integers in the sequence, whose sum of digits is divisible by 3 .

------ Constraints ------ 

$1 ≤T ≤10^{4}$
$1 ≤L ≤R ≤10^{18}$

------ subtasks ------ 

Subtask $1$ ($100$ points): Original constraints

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

5
139 141
100 1235
1000 2537
998244353 1000000007
27182818284 31415926535897
----- Sample Output 1 ------ 
1
378
512
585218
10462914572538
----- explanation 1 ------ 
Test case 1: The numbers are $139$, $140$ and $141$. Their sum of digits is $13$, $5$ and $6$ respectively. So, only $141$ is the number that has its sum of digits divisible by $3$.

Difficulty: MEDIUM
Tags: Number theory

Constructive algorithms

Mathematics

Ad-hoc

Starter code:

Solutions:
for tc in range(int(input())):
	(l, r) = map(int, input().split())
	lr = l % 3
	if lr:
		lr = 3 - lr
	rr = r % 3
	nl = l + lr
	nr = r - rr
	print((nr - nl) // 3 + 1)


t = int(input())
for t1 in range(t):
	(l, r) = map(int, input().split(' '))
	if (l % 3 != 0) & (r % 3 != 0):
		print((r - l + 1) // 3)
	else:
		print((r - l) // 3 + 1)


def find_count(start, end):
	reminder = start % 3
	start += 3 - reminder if reminder != 0 else 0
	end -= end % 3
	counter = (end - start) // 3 + 1
	return counter
number_of_test_cases = int(input())
for i in range(number_of_test_cases):
	inputs = input().split()
	start = int(inputs[0])
	end = int(inputs[1])
	print(find_count(start, end))


import math
for _ in range(int(input())):
	(l, r) = map(int, input().split())
	(p1, p2) = (math.ceil(l / 3), math.floor(r // 3))
	print(int(p2 - p1 + 1))


import math
t = input()
for c in range(0, int(t)):
	(l, r) = map(int, input().split())
	(p1, p2) = (math.ceil(l / 3), math.floor(r // 3))
	print(int(p2 - p1 + 1))


T = int(input())
for x in range(T):
	(l, r) = map(int, input().split())
	t = r - l + 1
	c = t // 3
	for i in range(t % 3):
		if (l + i) % 3 == 0:
			c += 1
			break
	print(c)


t = int(input())
for i in range(t):
	(l, r) = map(int, input().split())
	total = r - l + 1
	count = total // 3
	for i in range(total % 3):
		if (l + i) % 3 == 0:
			count += 1
			break
	print(count)


tests = int(input())
for i in range(tests):
	(l, r) = map(int, input().split())
	while l % 3 != 0:
		l += 1
	while r % 3 != 0:
		r -= 1
	ans = (r - l) // 3
	ans += 1
	print(ans)


t = int(input())
for i in range(t):
	(l, r) = map(int, input().split())
	print(r // 3 - (l - 1) // 3)


import math
for _ in range(int(input())):
	(l, r) = map(int, input().split())
	n = r - l + 1
	k = l % 3
	if k == 1:
		n = n
	elif k == 2:
		n = n + 1
	elif k == 0:
		n = n + 2
	ans = n // 3
	print(ans)


banyak_kasus = int(input())
while banyak_kasus > 0:
	(l, r) = list(map(int, input().split(' ')))
	banyak = r // 3 - l // 3
	if l % 3 == 0:
		banyak = r // 3 - l // 3 + 1
	print(banyak)
	banyak_kasus -= 1


for _ in range(int(input())):
	(L, R) = map(int, input().split())
	print(R // 3 - (L - 1) // 3)


for _ in range(int(input())):
	(L, R) = map(int, input().split())
	(S, E) = (0, 0)
	if L % 3 == 0:
		S = L
	elif L % 3 == 1:
		S = L + 2
	elif L % 3 == 2:
		S = L + 1
	if R % 3 == 0:
		E = R
	elif R % 3 == 1:
		E = R - 1
	elif R % 3 == 2:
		E = R - 2
	if S == E:
		print(1)
	elif S > E:
		print(0)
	else:
		print((E - S) // 3 + 1)


t = input()
t = int(t)
for i in range(t):
	(l, r) = map(int, input().split())
	dif = r // 3 - l // 3
	if l % 3 == 0:
		print(dif + 1)
	else:
		print(dif)


for _ in range(int(input())):
	(L, R) = map(int, input().split())
	ansr = R // 3
	ansl = L // 3
	if L % 3 == 0:
		print(ansr - ansl + 1)
	else:
		print(ansr - ansl)


t = int(input())
for test in range(t):
	(L, R) = list(map(int, input().split()))
	print(R // 3 - (L - 1) // 3)


z = int(input())
for i in range(z):
	(x, y) = map(int, input().split())
	a = (x - 1) // 3
	b = y // 3
	print(b - a)


t = int(input())
while t:
	t -= 1
	(l, r) = map(int, input().split())
	k = 0
	if l % 3 == 0:
		k += 1
	print(r // 3 - l // 3 + k)


t = int(input())
for _ in range(t):
	(l, r) = map(int, input().split())
	n = r - l + 1
	if n % 3 == 1 and (l % 3 == 0 or r % 3 == 0):
		print(n // 3 + 1)
	elif n % 3 == 2 and (l + 2) % 3 != 0:
		print(n // 3 + 1)
	else:
		print(n // 3)


import math
for _ in range(int(input())):
	(l, r) = list(map(int, input().split()))
	ans = r // 3 - (l - 1) // 3
	print(ans)


def solve(l, r):
	if l % 3 != 0:
		l += 3 - l % 3
	r -= r % 3
	return 1 + (r - l) // 3

def main():
	for _ in range(int(input())):
		(l, r) = map(int, input().split())
		result = solve(l, r)
		print(result)
main()


T = int(input())
for tj in range(T):
	(L, R) = map(int, input().split())
	if L % 3 != 0:
		print((R - L + L % 3) // 3)
	else:
		print((R - L) // 3 + 1)


t = int(input(''))
for tc in range(t):
	(l, r) = list(map(int, input().split()))
	if (r + 1 - l) // 3 >= 1:
		if l % 3 != 0:
			if l % 3 == 1:
				l = l + 2
			else:
				l = l + 1
		if r % 3 != 0:
			if r % 3 == 1:
				r = r - 1
			else:
				r = r - 2
		print((r - l) // 3 + 1)
	elif l % 3 == 0 or r % 3 == 0:
		print(1)
	else:
		print(0)


def count(l, r):
	c = r // 3 - (l - 1) // 3
	return c
t = int(input())
for i in range(t):
	lr = input().split()
	l = int(lr[0])
	r = int(lr[1])
	print(count(l, r))


n = int(input())
for i in range(n):
	(a, b) = map(int, input().split())
	x = b // 3 - (a - 1) // 3
	print(x)


for i in range(int(input())):
	q = 0
	w = 0
	(a, b) = map(int, input().split())
	for l in range(a, a + 4):
		if l % 3 == 0:
			q = l
			break
	for k in range(b, b - 4, -1):
		if k % 3 == 0:
			w = k
			break
	diff = w - q
	sol = diff // 3 + 1
	print(sol)


ans = ''
for _ in range(int(input())):
	(l, r) = list(map(int, input().split()))
	if l % 3 != 0:
		l = l + (3 - l % 3)
	if r % 3 != 0:
		r = r - r % 3
	count = (r - l) // 3 + 1
	ans += str(count) + '\n'
print(ans)


for _ in range(int(input())):
	(l, r) = map(int, input().split())
	(fr, bk) = (l if l % 3 == 0 else l + 1 if (l + 1) % 3 == 0 else l + 2, r if r % 3 == 0 else r - 1 if (r - 1) % 3 == 0 else r - 2)
	print((bk - fr) // 3 + 1)


for _ in range(int(input())):
	(l, r) = map(int, input().split())
	(a, b) = (l % 3, r % 3)
	if a != 0:
		l += 3 - a
	if l > r:
		print(0)
	else:
		r -= b
		print((r - l) // 3 + 1)


for _ in range(int(input())):
	(L, R) = map(int, input().split())
	D = R - L + 1
	if D % 3 == 0:
		print(D // 3)
	elif D % 3 == 1:
		if L % 3 == 0:
			print(D // 3 + 1)
		else:
			print(D // 3)
	elif D % 3 == 2:
		if (L + 1) % 3 == 0 or L % 3 == 0:
			print(D // 3 + 1)
		else:
			print(D // 3)


t = int(input())
for i in range(t):
	(l, r) = map(int, input().split())
	if l % 3 != 0:
		l += 3 - l % 3
	if r % 3 != 0:
		r -= r % 3
	ans = (r - l + 3) // 3
	print(ans)


for tc in range(int(input())):
	(f, l) = map(int, input().split())
	if f % 3 != 0:
		f += 3 - f % 3
	if l % 3 != 0:
		l -= l % 3
	ans = (l - f + 3) // 3
	print(ans)


try:
	for i in range(int(input())):
		(l, r) = map(int, input().split())
		n = r // 3 - l // 3
		if l % 3 == 0:
			n += 1
		print(n)
except:
	pass


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


from math import ceil
for i in range(int(input())):
	(a, b) = [int(x) for x in input().split()]
	start = str(a)
	cnt = 0
	sm = 0
	for j in range(len(start)):
		sm += int(start[j])
	rem1 = sm % 3
	cnt = 0
	sm = 0
	start = str(b)
	for j in range(len(start)):
		sm += int(start[j])
	rem2 = sm % 3
	print((b - a + 1 - rem1 - rem2) // 3 + 1)


ans = ''
for _ in range(int(input())):
	(l, r) = list(map(int, input().split()))
	i = l
	while i % 3 != 0:
		i += 1
	num = (r - i) // 3 + 1
	ans += str(num) + '\n'
print(ans)


for _ in range(int(input())):
	(l, r) = map(int, input().split())
	print(r // 3 - (l - 1) // 3)


from math import *
import sys

def input():
	return sys.stdin.readline().replace('\n', '').strip()
sys.setrecursionlimit(10 ** 9)

def calc(n):
	return n // 3
for _ in range(int(input())):
	(a, b) = list(map(int, input().split()))
	print(calc(b) - calc(a - 1))


def solve():
	(l, r) = map(int, input().split())
	return r // 3 - (l - 1) // 3
t = int(input())
while t:
	print(solve())
	t -= 1


T = int(input())
for i in range(T):
	(A, B) = map(int, input().split(' '))
	k = B // 3 - (A - 1) // 3
	print(k)


for i in range(int(input())):
	(x, y) = map(int, input().split())
	c = 0
	c = y // 3 - x // 3
	if x % 3 == 0:
		c = c + 1
	print(c)


tests = int(input())
for t0 in range(tests):
	[l, r] = [int(i) for i in input().split()]
	ans = r // 3 - l // 3
	if l % 3 == 0:
		ans += 1
	print(ans)


for i in range(int(input())):
	(a, b) = map(int, input().split())
	c = a // 3
	d = b // 3
	if a % 3 == 0:
		print(d - c + 1)
	else:
		print(d - c)


t = int(input())
for i in range(t):
	(a, b) = map(int, input().split())
	for i in range(3):
		if a % 3 == 0:
			break
		a = a + 1
	for i in range(3):
		if b % 3 == 0:
			break
		b = b - 1
	print((b - a) // 3 + 1)


import math
for _ in range(int(input())):
	(l, r) = map(int, input().split())
	for i in range(3):
		if l % 3 == 0:
			break
		else:
			l += 1
	for i in range(3):
		if r % 3 == 0:
			break
		else:
			r -= 1
	print((r - l) // 3 + 1)


for l in range(int(input())):
	(l, r) = [int(a) for a in input().split()]
	r1 = l // 3
	r2 = r // 3
	ans = 0
	if l % 3 == 0:
		ans = ans + 1
	print(ans + r2 - r1)


t = int(input())
while t != 0:
	t -= 1
	(x, y) = map(int, input().split())
	ct = 0
	x11 = x % 3
	if x11 == 0:
		x11 = 3
	x1 = 3 - x11 + x
	y1 = y - y % 3
	n = (y1 - x1) // 3
	print(n + 1)


for i in range(int(input())):
	(a, b) = [int(j) for j in input().split()]
	n = b - a + 1
	ans = n // 3
	if n % 3 == 1 and a % 3 == 0:
		ans += 1
	if n % 3 == 2 and a % 3 != 1:
		ans += 1
	print(ans)


T = int(input())
for i in range(T):
	(L, R) = map(int, input().split())
	if L % 3 == 0:
		lower = L
	else:
		lower = L + (3 - L % 3)
	upper = R - R % 3
	x = upper // 3
	y = lower // 3
	print(x - y + 1)


def check(l, r):
	if l % 3 == 0:
		a = l
	elif (l + 1) % 3 == 0:
		a = l + 1
	else:
		a = l + 2
	data = (r - a) // 3
	return data + 1
t = int(input())
for _ in range(t):
	(l, r) = map(int, input().split())
	print(check(l, r))


for i in range(int(input())):
	(a, b) = map(int, input().split())
	if a % 3 == 0:
		a -= 3
	a += 3 - a % 3
	b += 3 - b % 3
	print((b - a) // 3)


try:
	T = int(input())
	for i in range(T):
		(l, r) = list(map(int, input().split()))
		while l % 3 != 0:
			l += 1
		while r % 3 != 0:
			r -= 1
		num = (r - l) // 3 + 1
		print(num)
except:
	pass


test_case = int(input())
while test_case != 0:
	(l, r) = map(int, input().split())
	s = r // 3 - (l - 1) // 3
	print(s)
	test_case -= 1


t = int(input())
while t:
	(l, r) = map(int, input().split())
	print(r // 3 - (l - 1) // 3)
	t -= 1