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

During a boring night at the restaurant, Chef decided to play with spaghetti. He has $R-L+1$ spaghetti: exactly one spaghetti with each length between $L$ and $R$ inclusive.

Chef decided to take some of his spaghetti and stick them together to form one very long spaghetti. The length of this spaghetti is the sum of the lengths of the spaghetti he took. In particular, he may take all spaghetti and he may take only one spaghetti as well. How many different spaghetti can he make?

Two spaghetti are considered different if their lengths are different.

------  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 two space-separated integers $L$ and $R$.

------  Output ------
For each test case, print a single line containing one integer ― the number of different spaghetti Chef can make.

------  Constraints ------
$1 ≤ T ≤ 1,000$
$1 ≤ L, R ≤ 10^{9}$

------  Subtasks ------
Subtask #1 (25 points): $L = 1$

Subtask #2 (55 points): $L, R ≤ 10^{4}$

Subtask #3 (20 points): original constraints

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

1 2

3 5
----- Sample Output 1 ------ 
3

7

Difficulty: VERY_HARD
Tags: Mathematics

Greedy algorithms
Skill types: Greedy algorithms

Starter code:

Solutions:
import math

def squareSum(N):
	return N * (N + 1) * (2 * N + 1) // 6

def linearSum(N):
	return N * (N + 1) // 2

def getFunctionValue(A, B, C, L, R):
	if R < L:
		return 0
	dxx = squareSum(R) - squareSum(L - 1)
	dx = linearSum(R) - linearSum(L - 1)
	d = R - (L - 1)
	return A * dxx + B * dx + C * d

def phawinRoundDown(v):
	l = int(v)
	r = l + 1
	if r - v < 1e-06:
		return r
	else:
		return l

def phawinRoundUp(v):
	l = int(v)
	r = l + 1
	if v - l < 1e-06:
		return l
	else:
		return r

def solve(L, R):
	ALL = linearSum(R) - linearSum(L - 1)
	N = R - L + 1
	A = 1
	B = -(N + 1)
	C = L + N - 1
	if B * B - 4 * A * C <= 0:
		fv = getFunctionValue(A, B, C, 1, N)
		return ALL - fv
	else:
		sq = math.sqrt(B * B - 4 * A * C)
		k1 = (-B - sq) / 2
		k2 = (-B + sq) / 2
		k1 = min(phawinRoundDown(k1), N)
		k2 = max(phawinRoundUp(k2), 1)
		r1 = getFunctionValue(A, B, C, 1, k1)
		r2 = getFunctionValue(A, B, C, k2, N)
		return ALL - (r1 + r2)

def driver():
	TC = int(input())
	for run_id in range(TC):
		data = input().split()
		L = int(data[0])
		R = int(data[1])
		ans = solve(L, R)
		print(ans)
driver()


import sys
input = iter(sys.stdin.read().splitlines()).__next__

def Choose3(n):
	return n * (n - 1) * (n - 2) // 6

def A000125(n):
	return Choose3(n + 1) + n + 1

def sum_1toN(n):
	return n * (n + 1) // 2

def sum_1toN_squared(n):
	return n * (n + 1) * (2 * n + 1) // 6

def sum_odd_squares(n):
	return n * (4 * n * n - 1) // 3

def get_min_start(LEN):
	if LEN % 2 == 0:
		i = (LEN - 2) // 2
		return i * i + i + 1
	else:
		i = (LEN - 1) // 2
		return i * i + 1

def solve(L, R):
	assert L <= R
	LEN = R - L + 1
	if LEN == 1:
		return 2 - 1
	if LEN == 2:
		return 4 - 1
	res = A000125(LEN)
	min_start = get_min_start(LEN)
	if L < min_start:
		dif = min_start - L
		if LEN % 2 == 0:
			(lo, hi) = (1, 1000000000000000000)
			bs_res = 0
			while lo <= hi:
				mid = lo + (hi - lo) // 2
				if 2 * sum_1toN(mid) <= dif:
					lo = mid + 1
					bs_res = mid
				else:
					hi = mid - 1
			res -= 4 * sum_1toN_squared(bs_res)
			idx = min_start - 2 * sum_1toN(bs_res)
			step = (bs_res + 1) * 2
			res -= (idx - L) * step
		else:
			(lo, hi) = (1, 1000000000000000000)
			bs_res = 0
			while lo <= hi:
				mid = lo + (hi - lo) // 2
				if mid * mid <= dif:
					lo = mid + 1
					bs_res = mid
				else:
					hi = mid - 1
			res -= sum_odd_squares(bs_res)
			idx = min_start - bs_res * bs_res
			step = (bs_res + 1) * 2 - 1
			res -= (idx - L) * step
	res -= 1
	return res
TC = int(input())
for tc in range(TC):
	(L, R) = map(int, input().split())
	res = solve(L, R)
	print(res)


def ar(a, n):
	return (a + a + n - 1) * n // 2

def pref(l, r, ile):
	return ar(l, ile)

def suf(l, r, ile):
	return ar(r - ile + 1, ile)

def sumka(b, a, n):
	add = a * b * n
	add += n
	add -= n * (n - 1) * (2 * n - 1) // 6
	heh = b - a
	add += heh * (n - 1) * n // 2
	return add

def find_left(l, r, md):
	left = 1
	right = md + 1
	while left < right:
		mid = (left + right) // 2
		if pref(l, r, mid + 1) > suf(l, r, mid):
			left = mid + 1
		else:
			right = mid
	return left

def find_right(l, r, md):
	left = md
	right = r - l + 1
	while left < right:
		mid = (left + right) // 2
		if pref(l, r, mid + 1) > suf(l, r, mid):
			right = mid
		else:
			left = mid + 1
	return left

def xdd(l, r, a, b):
	if b < a:
		return 0
	ile = b - a + 1
	s1 = r - a + 1 - l
	ile1 = a
	return sumka(s1, ile1, ile)
t = int(input())
for asd in range(t):
	(l, r) = map(int, input().split())
	if l == r:
		print(1)
		continue
	md = (r - l + 1) // 2
	a = find_left(l, r, md)
	b = find_right(l, r, md)
	if a <= b:
		ans = 0
		ans += suf(l, r, b)
		ans -= pref(l, r, a) - 1
		ans += xdd(l, r, 1, a - 1)
		ans += xdd(l, r, b + 1, r - l + 1)
	else:
		ans = xdd(l, r, 1, r - l + 1)
	print(ans)