Read problems statements in Mandarin Chinese, Russian and Vietnamese as well. 

Chef likes inequalities. Please help him to solve next one.
Given four integers a, b, c, d. Find number of solutions x < y, where a ≤ x ≤ b and c ≤ y ≤ d and x, y integers.

------ Input ------ 

The first line contains an integer T denoting number of tests.
First line of each test case contains four positive integer numbers a, b, c and d.

------ Output ------ 

For each test case, output a single number each in separate line denoting number of integer solutions as asked in the problem.

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

$1 ≤ T ≤ 20 $
$1 ≤ a, b, c, d ≤ 10^{6}$

------ Subtasks ------ 

$Subtask #1: (30 points)  1 ≤ a, b, c, d ≤ 10^{3}.$
$Subtask #2: (70 points)  Original constraints.$

----- Sample Input 1 ------ 
1
2 3 3 4
----- Sample Output 1 ------ 
3
----- explanation 1 ------ 

----- Sample Input 2 ------ 
1
2 999999 1 1000000
----- Sample Output 2 ------ 
499998500001
----- explanation 2 ------

Difficulty: MEDIUM
Tags: Combinatorics

Mathematics

Starter code:

Solutions:
for _ in range(int(input())):
	(a, b, c, d) = map(int, input().split())
	if d <= a:
		ans = 0
	else:
		x = max(c, a + 1)
		ans = 0
		for y in range(x, d + 1):
			ans += min(y - 1, b) - a + 1
	print(ans)


def soln(a, b, c, d):
	if d <= a:
		return 0
	c = max(c, a + 1)
	res = 0
	for y in range(c, d + 1):
		res += min(y - 1, b) - a + 1
	return res
for _ in range(int(input())):
	(a, b, c, d) = map(int, input().split())
	print(soln(a, b, c, d))


tests = int(input())
for i in range(tests):
	(a, b, c, d) = map(int, input().split())
	if d <= a:
		ans = 0
	else:
		c = max(c, a)
		b = min(d, b)
		ans = (b - a + 1) * (d - c + 1)
		if c <= b:
			gap = b - c + 1
			ans -= gap * (gap + 1) // 2
	print(ans)


for _ in range(int(input())):
	(a, b, c, d) = map(int, input().split())
	count = 0
	if b < a or d < c:
		print(0)
	else:
		for i in range(a, b + 1):
			if i < d:
				count += d - max(c, i + 1) + 1
			else:
				break
		print(count)


from bisect import bisect_left, bisect_right
import math
from bisect import bisect_left
from heapq import heapify, heappush, heappop
from collections import deque
import sys
from math import gcd, sqrt, log10, log2, floor, ceil, sqrt
from collections import deque, defaultdict
input = sys.stdin.readline

def il():
	return [int(a) for a in input().strip().split()]

def ip():
	return input().strip()

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

def ot(in_p, *args, e=' '):
	if type(in_p) == list:
		print(*in_p, end=e)
	if type(in_p) == str or type(in_p) == int:
		print(in_p, end=e)
		for l in args:
			print(l, end=e)
	print()

def a_pwr_n(a, n, mod):
	if n == 1:
		return a % mod
	if n % 2 == 0:
		val = a_pwr_n(a, n // 2, mod)
		return val % mod * val % mod
	else:
		return a % mod * a_pwr_n(a, n - 1, mod) % mod

def rg(*ag):
	if len(ag) == 3:
		return range(ag[0], ag[1], ag[2])
	elif len(ag) == 2:
		return range(ag[0], ag[1])
	elif len(ag) == 1:
		return range(ag[0])
	else:
		raise 'invalid input'

def ispal(i, j, st):
	while i <= j:
		if st[i] == st[j]:
			i = i + 1
			j = j - 1
		else:
			return False
	return True
mod = 1000000000 + 7
dx = [-1, -2, 1, 2, 2, -2, -1, 1]
dy = [2, 1, 2, 1, -1, -1, -2, -2]
for i in range(ii()):
	(a, b, c, d) = il()
	s = 0
	for i in range(a, b + 1):
		if i < c:
			s += d - c + 1
		elif i < d:
			s += d - i
	print(s)


T = int(input(''))
for i in range(T):
	l1 = [int(c) for c in input('').split()]
	if l1[0] > l1[3]:
		print('0')
	else:
		if l1[1] > l1[3]:
			l1[1] = l1[3]
		if l1[1] < l1[2]:
			x = (l1[1] - l1[0] + 1) * (l1[3] - l1[2] + 1)
			print(x)
		elif l1[1] == l1[2]:
			x = (l1[1] - l1[0] + 1) * (l1[3] - l1[2] + 1)
			print(x - 1)
		elif l1[1] > l1[2]:
			if l1[0] <= l1[2]:
				x = (l1[2] - l1[0] + 1) * (l1[3] - l1[2] + 1) - 1
				x += (l1[1] - l1[2]) * l1[3] - l1[1] * (l1[1] + 1) // 2 + l1[2] * (l1[2] + 1) // 2
				print(x)
			else:
				x = (l1[1] - l1[0] + 1) * l1[3] - l1[1] * (l1[1] + 1) // 2 + (l1[0] - 1) * l1[0] // 2
				print(x)


t = int(input())
for tc in range(t):
	(a, b, c, d) = map(int, input().split())
	ans = 0
	for x in range(a, b + 1):
		if x < c:
			ans = ans + d - c + 1
		elif x >= c and x < d:
			ans = ans + d - x
	print(ans)


T = int(input())
for i in range(T):
	(a, b, c, d) = map(int, input().split())
	res = 0
	for x in range(a, b + 1):
		if x < c:
			res = res + d - c + 1
		elif x >= c and x < d:
			res = res + d - x
	print(res)


n = int(input())
for i in range(n):
	(a, b, c, d) = map(int, input().split())
	r = 0
	for j in range(a, b + 1):
		if j < c:
			r += d - c + 1
		elif j >= c and j < d:
			r += d - j
	print(r)


t = int(input())
for _ in range(t):
	(a, b, c, d) = map(int, input().split())
	res = 0
	for x in range(a, b + 1):
		if x < c:
			res += d - c + 1
		elif x >= c and x < d:
			res += d - x
	print(res)


t = int(input())
for _ in range(t):
	(a, b, c, d) = map(int, input().split())
	(a, b) = (min(a, b), max(a, b))
	(c, d) = (min(c, d), max(c, d))
	ans = 0
	for i in range(a, b + 1):
		if i < c:
			ans = d - c + 1 + ans
		elif i < d:
			ans = d - i + ans
	print(ans)


for _ in range(int(input())):
	(a, b, c, d) = map(int, input().split())
	ans = 0
	for k in range(a, b + 1):
		k = d - max(k + 1, c) + 1
		ans = ans + max(0, k)
	print(ans)


T = int(input())
for tj in range(T):
	(a, b, c, d) = map(int, input().split())
	if max(a, b) != b or max(c, d) != d:
		print(0)
	else:
		sum_v = 0
		for i in range(a, b + 1):
			if i < c:
				sum_v += d - c + 1
			else:
				sum_v += max(0, d - i)
		print(sum_v)


from math import *
import sys

def input():
	return sys.stdin.readline().replace('\n', '').strip()
sys.setrecursionlimit(10 ** 9)
for _ in range(int(input())):
	(a, b, c, d) = list(map(int, input().split()))
	ans = 0
	if b < c:
		ans = (b - a + 1) * (d - c + 1)
	else:
		for x in range(a, b + 1):
			min_req = x + 1
			ans += max(0, d - max(min_req, c) + 1)
	if a <= b and c <= d:
		print(ans)
	else:
		print(0)


for _ in range(int(input())):
	(a, b, c, d) = map(int, input().split())
	ans = 0
	if a <= b and c <= d and (d > a):
		for i in range(a, b + 1):
			if i < d:
				ans += d - max(c, i + 1) + 1
			else:
				break
	print(ans)


t = int(input())
for i in range(t):
	count = 0
	(a, b, c, d) = map(int, input().split())
	for i in range(a, b + 1):
		if i < c:
			count += d - c + 1
		elif i < d:
			count += d - i
	print(count)


for _ in range(int(input())):
	(a, b, c, d) = map(int, input().split())
	count = 0
	for j in range(a, b + 1):
		if j < c:
			count += d - c + 1
		elif j < d:
			count += d - j
	print(count)


n = int(input())
for i in range(n):
	(a, b, c, d) = map(int, input().split())
	sum = 0
	if b < a or d < c:
		print(0)
	else:
		for i in range(a, b + 1):
			if i < d:
				sum += d - max(c, i + 1) + 1
			else:
				break
	print(sum)


import sys
sys.setrecursionlimit(10 ** 5 + 1)
inf = int(10 ** 20)
max_val = inf
min_val = -inf
RW = lambda : sys.stdin.readline().strip()
RI = lambda : int(RW())
RMI = lambda : [int(x) for x in sys.stdin.readline().strip().split()]
RWI = lambda : [x for x in sys.stdin.readline().strip().split()]
for _ in range(RI()):
	(a, b, c, d) = RMI()
	count = 0
	if b < a or d < c:
		print(0)
	else:
		for i in range(a, b + 1):
			if i < d:
				count += d - max(c, i + 1) + 1
			else:
				break
		print(count)


for _ in range(int(input())):
	(a, b, c, d) = (int(i) for i in input().strip().split())
	res_cnt = 0
	for i in range(a, b + 1):
		temp = max(i, c - 1)
		if d > temp:
			res_cnt += d - temp
	print(res_cnt)


def inequalities(a, b, c, d):
	res = [d - max(c, i + 1) + 1 for i in range(a, b + 1) if max(c, i + 1) <= d]
	return sum(res)
t = int(input())
for i in range(t):
	(a, b, c, d) = map(int, input().split())
	print(inequalities(a, b, c, d))


t = int(input())
for _ in range(t):
	(a, b, c, d) = [int(x) for x in input().split()]
	ans = 0
	for i in range(a, b + 1):
		if i < c:
			ans += d - c + 1
		elif i < d:
			ans += d - i
	print(ans)


for _ in range(int(input())):
	(a, b, c, d) = map(int, input().split())
	sum = 0
	for i in range(a, b + 1):
		if i < c:
			sum += d - c + 1
		elif i < d:
			sum += d - i
	print(sum)


for _ in range(int(input())):
	(a, b, c, d) = tuple(map(int, input().split()))
	m = range(a, b + 1)
	n = range(c, d + 1)
	count = 0
	for i in n:
		if i > a and i <= b:
			count += i - a
		elif i > a and i > b:
			count += b - a + 1
		elif i < a and i < b:
			count = count
	print(count)


def Cook(a, b, c, d):
	ans = 0
	for i in range(a, b + 1):
		left = max(c, i + 1)
		if left <= d:
			ans += d - left + 1
	return ans
for T in range(int(input())):
	(a, b, c, d) = map(int, input().split())
	print(Cook(a, b, c, d))


t = int(input())
for i in range(t):
	arr = list(map(int, input().split()))
	a = arr[0]
	b = arr[1]
	c = arr[2]
	d = arr[3]
	count = 0
	for j in range(a, b + 1):
		if j < d:
			if j < c:
				count += d - c + 1
			else:
				count += d - j
	print(count)


t = int(input())
for i in range(t):
	l = input().split(' ')
	a = int(l[0])
	b = int(l[1])
	c = int(l[2])
	d = int(l[3])
	temp = b
	ans = 0
	count = b - a + 1
	while c <= d and a <= b:
		if b < d:
			ans = ans + count
			d -= 1
		else:
			b -= 1
			count -= 1
	print(ans)


t = int(input())
for _ in range(t):
	(a, b, c, d) = map(int, input().split())
	res = 0
	for x in range(a, b + 1):
		res += max(d - max(c, x + 1) + 1, 0)
	print(res)


for _ in range(int(input())):
	(a, b, c, d) = map(int, input().split())
	answer = 0
	for i in range(a, b + 1):
		if d >= max(c, i + 1):
			answer += d - max(c, i + 1) + 1
	print(answer)