You need to count the number of quadruples of integers (X_{1}, X_{2}, X_{3}, X_{4}),
such that L_{i} ≤ X_{i} ≤ R_{i} for i = 1, 2, 3, 4
and X_{1} ≠ X_{2}, X_{2} ≠ X_{3},
X_{3} ≠ X_{4}, X_{4} ≠ X_{1}.

The answer could be quite large. 

Hence you should output it modulo (10^{9} + 7). 

That is, you need to find the remainder of the answer by (10^{9} + 7).

Input Format 

The first line of the input contains an integer T denoting the number of test cases.
The description of T test cases follows.
The only line of each test case contains 8 space-separated integers
L_{1}, R_{1}, L_{2}, R_{2}, L_{3}, R_{3}, L_{4}, R_{4}, in order.

Output Format 

For each test case, output a single line containing the number of required quadruples modulo (10^{9} + 7).

Constraints 

1 ≤ T ≤ 1000 

1 ≤ L_{i} ≤ R_{i} ≤ 10^{9}

Sample Input

5
1 4 1 3 1 2 4 4
1 3 1 2 1 3 3 4
1 3 3 4 2 4 1 4
1 1 2 4 2 3 3 4
3 3 1 2 2 3 1 2

Sample Output  

8
10
23
6
5

Explanation 

Example case 1. All quadruples in this case are

1 2 1 4
1 3 1 4
1 3 2 4
2 1 2 4
2 3 1 4
2 3 2 4
3 1 2 4
3 2 1 4

Example case 2. All quadruples in this case are

1 2 1 3
1 2 1 4
1 2 3 4
2 1 2 3
2 1 2 4
2 1 3 4
3 1 2 4
3 1 3 4
3 2 1 4
3 2 3 4

Example case 3. All quadruples in this case are

1 3 2 3
1 3 2 4
1 3 4 2
1 3 4 3
1 4 2 3
1 4 2 4
1 4 3 2
1 4 3 4
2 3 2 1
2 3 2 3
2 3 2 4
2 3 4 1
2 3 4 3
2 4 2 1
2 4 2 3
2 4 2 4
2 4 3 1
2 4 3 4
3 4 2 1
3 4 2 4
3 4 3 1
3 4 3 2
3 4 3 4

Example case 4. All quadruples in this case are

1 2 3 4
1 3 2 3
1 3 2 4
1 4 2 3
1 4 2 4
1 4 3 4

Example case 5. All quadruples in this case are

3 1 2 1
3 1 3 1
3 1 3 2
3 2 3 1
3 2 3 2

Difficulty: MEDIUM
Tags: Combinatorics

Starter code:

Solutions:
p = int(1000000000.0 + 7)

def intsc(l1, l2):
	if l1 == [] or l2 == []:
		return []
	else:
		a = max(l1[0], l2[0])
		b = min(l1[1], l2[1])
		if b < a:
			return []
		else:
			return [a, b]

def cd(l):
	if l == []:
		return 0
	else:
		return l[1] - l[0] + 1
t = int(input())
for tst in range(t):
	s = input().strip().split()
	w = []
	for i in s:
		w.append(int(i))
	z = {}
	z[0] = [w[0], w[1]]
	z[1] = [w[2], w[3]]
	z[2] = [w[4], w[5]]
	z[3] = [w[6], w[7]]
	comp = 0
	for i in range(4):
		tmp = 1
		L = intsc(z[i], z[(i + 1) % 4])
		j = (i + 2) % 4
		k = (i + 3) % 4
		tmp = tmp * cd(L) % p
		tmp = tmp * cd(z[j]) % p
		tmp = tmp * cd(z[k]) % p
		comp = (comp + tmp) % p
	for i in range(4):
		tmp = 1
		L = intsc(z[i], z[(i + 1) % 4])
		L = intsc(L, z[(i + 2) % 4])
		tmp = cd(L) % p
		tmp = tmp * cd(z[(i + 3) % 4]) % p
		comp = (comp - tmp) % p
	a1 = intsc(z[0], z[1])
	a2 = intsc(z[2], z[3])
	a3 = intsc(z[1], z[2])
	a4 = intsc(z[3], z[0])
	comp = (comp - cd(a1) * cd(a2) % p) % p
	comp = (comp - cd(a3) * cd(a4) % p) % p
	b = intsc(a1, a2)
	comp = (comp + 3 * cd(b)) % p
	tot = 1
	for i in range(4):
		tot *= cd(z[i])
		tot %= p
	tot -= comp
	tot %= p
	print(tot)


import functools, itertools, operator as op, sys
MOD = 1000000007
N = 4

class Interval:

	def __init__(self, L, R):
		self.L = L
		self.R = R

	def __len__(self):
		if self.L is not None and self.R is not None:
			return self.R - self.L + 1
		else:
			return 0

	def __repr__(self):
		return '[%d, %d]' % (self.L, self.R)

	def overlaps(self, I):
		if self and I:
			return self.L <= I.R and self.R >= I.L
		else:
			return False

	def intersect(self, I):
		if self and I and self.overlaps(I):
			return Interval(max(self.L, I.L), min(self.R, I.R))
		else:
			return Interval(None, None)
T = int(sys.stdin.readline())
for _ in range(T):
	I = [Interval(*x) for x in zip(*[map(int, sys.stdin.readline().split())] * 2)]
	total = functools.reduce(op.mul, map(len, I))
	for i in range(N):
		total -= len(I[i].intersect(I[(i + 1) % N])) * len(I[(i + 2) % N]) * len(I[(i + 3) % N])
	for i in range(N):
		total += len(I[i].intersect(I[(i + 1) % N]).intersect(I[(i + 2) % N])) * len(I[(i + 3) % N])
	for i in range(N // 2):
		total += len(I[i].intersect(I[(i + 1) % N])) * len(I[(i + 2) % N].intersect(I[(i + 3) % N]))
	for i in range(N):
		total -= len(I[i].intersect(I[(i + 1) % N]).intersect(I[(i + 2) % N]).intersect(I[(i + 3) % N]))
	total += len(I[0].intersect(I[1]).intersect(I[2]).intersect(I[3]))
	print(total % MOD)


import functools, itertools, operator as op, sys
MOD = 1000000007
N = 4

class Interval:

	def __init__(self, L, R):
		self.L = L
		self.R = R

	def __len__(self):
		if self.L is not None and self.R is not None:
			return self.R - self.L + 1
		else:
			return 0

	def __repr__(self):
		return '[%d, %d]' % (self.L, self.R)

	def overlaps(self, I):
		if self and I:
			return self.L <= I.R and self.R >= I.L
		else:
			return False

	def intersect(self, I):
		if self and I and self.overlaps(I):
			return Interval(max(self.L, I.L), min(self.R, I.R))
		else:
			return Interval(None, None)
T = int(sys.stdin.readline())
for _ in range(T):
	I = [Interval(*x) for x in zip(*[map(int, sys.stdin.readline().split())] * 2)]
	total = functools.reduce(op.mul, map(len, I))
	for i in range(N):
		total -= len(I[i].intersect(I[(i + 1) % N])) * len(I[(i + 2) % N]) * len(I[(i + 3) % N])
	for i in range(N):
		total += len(I[i].intersect(I[(i + 1) % N]).intersect(I[(i + 2) % N])) * len(I[(i + 3) % N])
	for i in range(N // 2):
		total += len(I[i].intersect(I[(i + 1) % N])) * len(I[(i + 2) % N].intersect(I[(i + 3) % N]))
	for i in range(N):
		total -= len(I[i].intersect(I[(i + 1) % N]).intersect(I[(i + 2) % N]).intersect(I[(i + 3) % N]))
	total += len(I[0].intersect(I[1]).intersect(I[2]).intersect(I[3]))
	print(total % MOD)


import functools, itertools, operator as op, sys
MOD = 1000000007
N = 4

class Interval:

	def __init__(self, L, R):
		self.L = L
		self.R = R

	def __len__(self):
		if self.L is not None and self.R is not None:
			return self.R - self.L + 1
		else:
			return 0

	def __repr__(self):
		return '[%d, %d]' % (self.L, self.R)

	def overlaps(self, I):
		if self and I:
			return self.L <= I.R and self.R >= I.L
		else:
			return False

	def intersect(self, I):
		if self and I and self.overlaps(I):
			return Interval(max(self.L, I.L), min(self.R, I.R))
		else:
			return Interval(None, None)
T = int(sys.stdin.readline())
for _ in range(T):
	I = [Interval(*x) for x in zip(*[map(int, sys.stdin.readline().split())] * 2)]
	total = functools.reduce(op.mul, map(len, I))
	for i in range(N):
		total -= len(I[i].intersect(I[(i + 1) % N])) * len(I[(i + 2) % N]) * len(I[(i + 3) % N])
	for i in range(N):
		total += len(I[i].intersect(I[(i + 1) % N]).intersect(I[(i + 2) % N])) * len(I[(i + 3) % N])
	for i in range(N // 2):
		total += len(I[i].intersect(I[(i + 1) % N])) * len(I[(i + 2) % N].intersect(I[(i + 3) % N]))
	for i in range(N):
		total -= len(I[i].intersect(I[(i + 1) % N]).intersect(I[(i + 2) % N]).intersect(I[(i + 3) % N]))
	total += len(I[0].intersect(I[1]).intersect(I[2]).intersect(I[3]))
	print(total % MOD)


import functools, itertools, operator as op, sys
MOD = 1000000007
N = 4

class Interval:

	def __init__(self, L, R):
		self.L = L
		self.R = R

	def __len__(self):
		if self.L is not None and self.R is not None:
			return self.R - self.L + 1
		else:
			return 0

	def __repr__(self):
		return '[%d, %d]' % (self.L, self.R)

	def overlaps(self, I):
		if self and I:
			return self.L <= I.R and self.R >= I.L
		else:
			return False

	def intersect(self, I):
		if self and I and self.overlaps(I):
			return Interval(max(self.L, I.L), min(self.R, I.R))
		else:
			return Interval(None, None)
T = int(sys.stdin.readline())
for _ in range(T):
	I = [Interval(*x) for x in zip(*[map(int, sys.stdin.readline().split())] * 2)]
	total = functools.reduce(op.mul, map(len, I))
	for i in range(N):
		total -= len(I[i].intersect(I[(i + 1) % N])) * len(I[(i + 2) % N]) * len(I[(i + 3) % N])
	for i in range(N):
		total += len(I[i].intersect(I[(i + 1) % N]).intersect(I[(i + 2) % N])) * len(I[(i + 3) % N])
	for i in range(N // 2):
		total += len(I[i].intersect(I[(i + 1) % N])) * len(I[(i + 2) % N].intersect(I[(i + 3) % N]))
	for i in range(N):
		total -= len(I[i].intersect(I[(i + 1) % N]).intersect(I[(i + 2) % N]).intersect(I[(i + 3) % N]))
	total += len(I[0].intersect(I[1]).intersect(I[2]).intersect(I[3]))
	print(total % MOD)


import functools, itertools, operator as op, sys
MOD = 1000000007
N = 4

class Interval:

	def __init__(self, L, R):
		self.L = L
		self.R = R

	def __len__(self):
		if self.L is not None and self.R is not None:
			return self.R - self.L + 1
		else:
			return 0

	def __repr__(self):
		return '[%d, %d]' % (self.L, self.R)

	def overlaps(self, I):
		if self and I:
			return self.L <= I.R and self.R >= I.L
		else:
			return False

	def intersect(self, I):
		if self and I and self.overlaps(I):
			return Interval(max(self.L, I.L), min(self.R, I.R))
		else:
			return Interval(None, None)
T = int(sys.stdin.readline())
for _ in range(T):
	I = [Interval(*x) for x in zip(*[map(int, sys.stdin.readline().split())] * 2)]
	total = functools.reduce(op.mul, map(len, I))
	for i in range(N):
		total -= len(I[i].intersect(I[(i + 1) % N])) * len(I[(i + 2) % N]) * len(I[(i + 3) % N])
	for i in range(N):
		total += len(I[i].intersect(I[(i + 1) % N]).intersect(I[(i + 2) % N])) * len(I[(i + 3) % N])
	for i in range(N // 2):
		total += len(I[i].intersect(I[(i + 1) % N])) * len(I[(i + 2) % N].intersect(I[(i + 3) % N]))
	for i in range(N):
		total -= len(I[i].intersect(I[(i + 1) % N]).intersect(I[(i + 2) % N]).intersect(I[(i + 3) % N]))
	total += len(I[0].intersect(I[1]).intersect(I[2]).intersect(I[3]))
	print(total % MOD)


import functools, itertools, operator as op, sys
MOD = 1000000007
N = 4

class Interval:

	def __init__(self, L, R):
		self.L = L
		self.R = R

	def __len__(self):
		if self.L is not None and self.R is not None:
			return self.R - self.L + 1
		else:
			return 0

	def __repr__(self):
		return '[%d, %d]' % (self.L, self.R)

	def overlaps(self, I):
		if self and I:
			return self.L <= I.R and self.R >= I.L
		else:
			return False

	def intersect(self, I):
		if self and I and self.overlaps(I):
			return Interval(max(self.L, I.L), min(self.R, I.R))
		else:
			return Interval(None, None)
T = int(sys.stdin.readline())
for _ in range(T):
	I = [Interval(*x) for x in zip(*[map(int, sys.stdin.readline().split())] * 2)]
	total = functools.reduce(op.mul, map(len, I))
	for i in range(N):
		total -= len(I[i].intersect(I[(i + 1) % N])) * len(I[(i + 2) % N]) * len(I[(i + 3) % N])
	for i in range(N):
		total += len(I[i].intersect(I[(i + 1) % N]).intersect(I[(i + 2) % N])) * len(I[(i + 3) % N])
	for i in range(N // 2):
		total += len(I[i].intersect(I[(i + 1) % N])) * len(I[(i + 2) % N].intersect(I[(i + 3) % N]))
	for i in range(N):
		total -= len(I[i].intersect(I[(i + 1) % N]).intersect(I[(i + 2) % N]).intersect(I[(i + 3) % N]))
	total += len(I[0].intersect(I[1]).intersect(I[2]).intersect(I[3]))
	print(total % MOD)


import functools, itertools, operator as op, sys
MOD = 1000000007
N = 4

class Interval:

	def __init__(self, L, R):
		self.L = L
		self.R = R

	def __len__(self):
		if self.L is not None and self.R is not None:
			return self.R - self.L + 1
		else:
			return 0

	def __repr__(self):
		return '[%d, %d]' % (self.L, self.R)

	def overlaps(self, I):
		if self and I:
			return self.L <= I.R and self.R >= I.L
		else:
			return False

	def intersect(self, I):
		if self and I and self.overlaps(I):
			return Interval(max(self.L, I.L), min(self.R, I.R))
		else:
			return Interval(None, None)
T = int(sys.stdin.readline())
for _ in range(T):
	I = [Interval(*x) for x in zip(*[map(int, sys.stdin.readline().split())] * 2)]
	total = functools.reduce(op.mul, map(len, I))
	for i in range(N):
		total -= len(I[i].intersect(I[(i + 1) % N])) * len(I[(i + 2) % N]) * len(I[(i + 3) % N])
	for i in range(N):
		total += len(I[i].intersect(I[(i + 1) % N]).intersect(I[(i + 2) % N])) * len(I[(i + 3) % N])
	for i in range(N // 2):
		total += len(I[i].intersect(I[(i + 1) % N])) * len(I[(i + 2) % N].intersect(I[(i + 3) % N]))
	for i in range(N):
		total -= len(I[i].intersect(I[(i + 1) % N]).intersect(I[(i + 2) % N]).intersect(I[(i + 3) % N]))
	total += len(I[0].intersect(I[1]).intersect(I[2]).intersect(I[3]))
	print(total % MOD)


import functools, itertools, operator as op, sys
MOD = 1000000007
N = 4

class Interval:

	def __init__(self, L, R):
		self.L = L
		self.R = R

	def __len__(self):
		if self.L is not None and self.R is not None:
			return self.R - self.L + 1
		else:
			return 0

	def __repr__(self):
		return '[%d, %d]' % (self.L, self.R)

	def overlaps(self, I):
		if self and I:
			return self.L <= I.R and self.R >= I.L
		else:
			return False

	def intersect(self, I):
		if self and I and self.overlaps(I):
			return Interval(max(self.L, I.L), min(self.R, I.R))
		else:
			return Interval(None, None)
T = int(sys.stdin.readline())
for _ in range(T):
	I = [Interval(*x) for x in zip(*[map(int, sys.stdin.readline().split())] * 2)]
	total = functools.reduce(op.mul, map(len, I))
	for i in range(N):
		total -= len(I[i].intersect(I[(i + 1) % N])) * len(I[(i + 2) % N]) * len(I[(i + 3) % N])
	for i in range(N):
		total += len(I[i].intersect(I[(i + 1) % N]).intersect(I[(i + 2) % N])) * len(I[(i + 3) % N])
	for i in range(N // 2):
		total += len(I[i].intersect(I[(i + 1) % N])) * len(I[(i + 2) % N].intersect(I[(i + 3) % N]))
	for i in range(N):
		total -= len(I[i].intersect(I[(i + 1) % N]).intersect(I[(i + 2) % N]).intersect(I[(i + 3) % N]))
	total += len(I[0].intersect(I[1]).intersect(I[2]).intersect(I[3]))
	print(total % MOD)


from functools import reduce
from operator import mul
L = [0] * 5
R = [0] * 5
rng = [1] * 5
all_i = [1, 2, 3, 4]

def overlap(i_list):
	return max(0, min((R[i] for i in i_list)) - max((L[i] for i in i_list)) + 1)
for _ in range(int(input())):
	(L[1], R[1], L[2], R[2], L[3], R[3], L[4], R[4]) = map(int, input().split())
	for i in all_i:
		rng[i] = R[i] - L[i] + 1
	answer = reduce(mul, rng) - 3 * overlap(all_i) + overlap([1, 2]) * overlap([3, 4]) + overlap([2, 3]) * overlap([1, 4])
	for j in range(4):
		answer += overlap([all_i[j], all_i[j - 1], all_i[j - 2]]) * rng[all_i[j - 3]]
		answer -= overlap([all_i[j], all_i[j - 1]]) * rng[all_i[j - 3]] * rng[all_i[j - 2]]
	print(answer % 1000000007)


import functools, itertools, operator as op, sys
MOD = 1000000007
N = 4

class Interval:

	def __init__(self, L, R):
		self.L = L
		self.R = R

	def __len__(self):
		if self.L is not None and self.R is not None:
			return self.R - self.L + 1
		else:
			return 0

	def __repr__(self):
		return '[%d, %d]' % (self.L, self.R)

	def overlaps(self, I):
		if self and I:
			return self.L <= I.R and self.R >= I.L
		else:
			return False

	def intersect(self, I):
		if self and I and self.overlaps(I):
			return Interval(max(self.L, I.L), min(self.R, I.R))
		else:
			return Interval(None, None)
T = int(sys.stdin.readline())
for _ in range(T):
	I = [Interval(*x) for x in zip(*[map(int, sys.stdin.readline().split())] * 2)]
	total = functools.reduce(op.mul, map(len, I))
	for i in range(N):
		total -= len(I[i].intersect(I[(i + 1) % N])) * len(I[(i + 2) % N]) * len(I[(i + 3) % N])
	for i in range(N):
		total += len(I[i].intersect(I[(i + 1) % N]).intersect(I[(i + 2) % N])) * len(I[(i + 3) % N])
	for i in range(N // 2):
		total += len(I[i].intersect(I[(i + 1) % N])) * len(I[(i + 2) % N].intersect(I[(i + 3) % N]))
	for i in range(N):
		total -= len(I[i].intersect(I[(i + 1) % N]).intersect(I[(i + 2) % N]).intersect(I[(i + 3) % N]))
	total += len(I[0].intersect(I[1]).intersect(I[2]).intersect(I[3]))
	print(total % MOD)


M = 1000000007

def cnt(p):
	return (p[1] - p[0] + 1) % M if p[0] <= p[1] else 0
p1 = [0, 0]
p2 = [0, 0]
p3 = [0, 0]
p4 = [0, 0]
for _ in range(int(input().strip())):
	(p1[0], p1[1], p2[0], p2[1], p3[0], p3[1], p4[0], p4[1]) = map(int, input().split())
	tot1 = cnt(p1) * cnt(p2) % M * (cnt(p3) * cnt(p4) % M) % M
	tot2 = cnt([max(p1[0], p2[0]), min(p1[1], p2[1])]) * (cnt(p3) * cnt(p4)) % M % M
	tot2 += cnt([max(p1[0], p4[0]), min(p1[1], p4[1])]) * (cnt(p2) * cnt(p3)) % M % M
	tot2 += cnt([max(p3[0], p2[0]), min(p3[1], p2[1])]) * (cnt(p1) * cnt(p4)) % M % M
	tot2 += cnt([max(p3[0], p4[0]), min(p3[1], p4[1])]) * (cnt(p1) * cnt(p2)) % M % M
	tot3 = cnt([max(p1[0], max(p2[0], p3[0])), min(p1[1], min(p2[1], p3[1]))]) * cnt(p4) % M
	tot3 += cnt([max(p1[0], max(p2[0], p4[0])), min(p1[1], min(p2[1], p4[1]))]) * cnt(p3) % M
	tot3 += cnt([max(p1[0], max(p3[0], p4[0])), min(p1[1], min(p3[1], p4[1]))]) * cnt(p2) % M
	tot3 += cnt([max(p1[0], p2[0]), min(p1[1], p2[1])]) * cnt([max(p3[0], p4[0]), min(p3[1], p4[1])]) % M
	tot3 += cnt([max(p1[0], p4[0]), min(p1[1], p4[1])]) * cnt([max(p3[0], p2[0]), min(p3[1], p2[1])]) % M
	tot3 += cnt([max(p4[0], max(p2[0], p3[0])), min(p4[1], min(p2[1], p3[1]))]) * cnt(p1) % M
	tot4 = 3 * cnt([max(max(p1[0], p4[0]), max(p2[0], p3[0])), min(min(p1[1], p4[1]), min(p2[1], p3[1]))]) % M
	tot1 = (tot1 - tot2 + tot3 - tot4) % M
	if tot1 < 0:
		tot1 += M
	print(tot1)


from functools import reduce

def joint(x, y):
	return (max(x[0], y[0]), min(x[1], y[1]))

def dist(seg):
	return max(0, seg[1] - seg[0])
MOD = 10 ** 9 + 7
a = [(0, 0) for i in range(4)]
for _ in range(int(input())):
	tot = 1
	line = list(map(int, input().split()))
	for i in range(4):
		a[i] = (line[2 * i], line[2 * i + 1] + 1)
		tot *= dist(a[i])
	for i in range(4):
		seg = joint(a[i], a[(i + 1) % 4])
		tot -= dist(seg) * dist(a[(i + 2) % 4]) * dist(a[(i + 3) % 4])
		tot %= MOD
	for i in range(4):
		seg = joint(joint(a[i], a[(i + 1) % 4]), a[(i + 2) % 4])
		tot += dist(seg) * dist(a[(i + 3) % 4])
		tot %= MOD
	for i in range(2):
		seg1 = joint(a[i], a[(i + 1) % 4])
		seg2 = joint(a[(i + 2) % 4], a[(i + 3) % 4])
		tot += dist(seg1) * dist(seg2)
		tot %= MOD
	seg = reduce(lambda x, y: joint(x, y), a, a[0])
	tot -= 3 * dist(seg)
	tot %= MOD
	print(tot)


import functools, itertools, operator as op, sys
MOD = 1000000007
N = 4

class Interval:

	def __init__(self, L, R):
		self.L = L
		self.R = R

	def __len__(self):
		if self.L is not None and self.R is not None:
			return self.R - self.L + 1
		else:
			return 0

	def __repr__(self):
		return '[%d, %d]' % (self.L, self.R)

	def overlaps(self, I):
		if self and I:
			return self.L <= I.R and self.R >= I.L
		else:
			return False

	def intersect(self, I):
		if self and I and self.overlaps(I):
			return Interval(max(self.L, I.L), min(self.R, I.R))
		else:
			return Interval(None, None)
T = int(sys.stdin.readline())
for _ in range(T):
	I = [Interval(*x) for x in zip(*[map(int, sys.stdin.readline().split())] * 2)]
	total = functools.reduce(op.mul, map(len, I))
	for i in range(N):
		total -= len(I[i].intersect(I[(i + 1) % N])) * len(I[(i + 2) % N]) * len(I[(i + 3) % N])
	for i in range(N):
		total += len(I[i].intersect(I[(i + 1) % N]).intersect(I[(i + 2) % N])) * len(I[(i + 3) % N])
	for i in range(N // 2):
		total += len(I[i].intersect(I[(i + 1) % N])) * len(I[(i + 2) % N].intersect(I[(i + 3) % N]))
	for i in range(N):
		total -= len(I[i].intersect(I[(i + 1) % N]).intersect(I[(i + 2) % N]).intersect(I[(i + 3) % N]))
	total += len(I[0].intersect(I[1]).intersect(I[2]).intersect(I[3]))
	print(total % MOD)


def rangeSize(l, r):
	if r < l:
		return 0
	return r - l + 1

def intersection(l1, r1, l2, r2):
	l3 = max(l1, l2)
	r3 = min(r1, r2)
	return (l3, r3)

def solve(l1, r1, l2, r2, l3, r3, l4, r4):
	allQuadraples = rangeSize(l1, r1) * rangeSize(l2, r2) * rangeSize(l3, r3) * rangeSize(l4, r4)
	(l12, r12) = intersection(l1, r1, l2, r2)
	(l23, r23) = intersection(l2, r2, l3, r3)
	(l34, r34) = intersection(l3, r3, l4, r4)
	(l41, r41) = intersection(l4, r4, l1, r1)
	(l123, r123) = intersection(l12, r12, l3, r3)
	(l234, r234) = intersection(l2, r2, l34, r34)
	(l134, r134) = intersection(l1, r1, l34, r34)
	(l124, r124) = intersection(l2, r2, l41, r41)
	(l1234, r1234) = intersection(l123, r123, l4, r4)
	invalidQuadraples = rangeSize(l12, r12) * rangeSize(l3, r3) * rangeSize(l4, r4) + rangeSize(l23, r23) * rangeSize(l1, r1) * rangeSize(l4, r4) + rangeSize(l34, r34) * rangeSize(l1, r1) * rangeSize(l2, r2) + rangeSize(l41, r41) * rangeSize(l2, r2) * rangeSize(l3, r3) - rangeSize(l123, r123) * rangeSize(l4, r4) - rangeSize(l234, r234) * rangeSize(l1, r1) - rangeSize(l134, r134) * rangeSize(l2, r2) - rangeSize(l124, r124) * rangeSize(l3, r3) - rangeSize(l23, r23) * rangeSize(l41, r41) - rangeSize(l12, r12) * rangeSize(l34, r34) + 3 * rangeSize(l1234, r1234)
	return (allQuadraples - invalidQuadraples) % (10 ** 9 + 7)
for _ in range(int(input())):
	(l1, r1, l2, r2, l3, r3, l4, r4) = map(int, input().split())
	print(solve(l1, r1, l2, r2, l3, r3, l4, r4))


num_q = int(input())

def c(X):
	left = max([x[0] for x in X])
	right = min([x[1] for x in X])
	rv = max(0, right - left + 1)
	return rv
mod = 1000000007
for _ in range(num_q):
	(a1, b1, a2, b2, a3, b3, a4, b4) = (int(x) for x in input().split())
	x = [[a1, b1], [a2, b2], [a3, b3], [a4, b4]]
	rv = c([x[0]]) * c([x[1]]) * c([x[2]]) * c([x[3]])
	rv = rv - c([x[0], x[1]]) * c([x[2]]) * c([x[3]])
	rv = rv - c([x[1], x[2]]) * c([x[3]]) * c([x[0]])
	rv = rv - c([x[2], x[3]]) * c([x[0]]) * c([x[1]])
	rv = rv - c([x[3], x[0]]) * c([x[1]]) * c([x[2]])
	rv = rv + c([x[0], x[1], x[2]]) * c([x[3]])
	rv = rv + c([x[1], x[2], x[3]]) * c([x[0]])
	rv = rv + c([x[2], x[3], x[0]]) * c([x[1]])
	rv = rv + c([x[3], x[0], x[1]]) * c([x[2]])
	rv = rv + c([x[0], x[1]]) * c([x[2], x[3]])
	rv = rv + c([x[3], x[0]]) * c([x[1], x[2]])
	rv = rv - 3 * c(x)
	print(rv % mod)


def mprod(a):
	p = 1
	for x in a:
		p = p * x % m
	return p

def fi(a):
	c = 0
	id = [0, 2, 4, 6]
	d = [a[i + 1] - a[i] + 1 for i in id]
	p = [min(a[i + 1], a[(i + 3) % 8]) - max(a[i], a[(i + 2) % 8]) + 1 for i in id]
	p = [x if x > 0 else 0 for x in p]
	r2 = [mprod([p[i], d[(i + 2) % 4], d[(i + 3) % 4]]) for i in range(4)]
	p2 = [min(a[i + 1], a[(i + 3) % 8], a[(i + 5) % 8]) - max(a[i], a[(i + 2) % 8], a[(i + 4) % 8]) + 1 for i in id]
	p2 = [x if x > 0 else 0 for x in p2]
	r3 = [mprod([p2[i], d[(i + 3) % 4]]) for i in range(4)] + [mprod([p[0], p[2]]), mprod([p[1] * p[3]])]
	p3 = min([a[i + 1] for i in id]) - max([a[i] for i in id]) + 1
	if p3 < 0:
		p3 = 0
	c = (3 * m + mprod(d) - sum(r2) + sum(r3) - 3 * p3) % m
	return c
t = int(input())
m = 1000000007
for test_case in range(t):
	a = list(map(int, input().rstrip().split()))
	print(fi(a))


from functools import reduce
from operator import mul
L = [0] * 5
R = [0] * 5
rng = [1] * 5
all_i = [1, 2, 3, 4]

def overlap(i_list):
	return max(0, min((R[i] for i in i_list)) - max((L[i] for i in i_list)) + 1)
for _ in range(int(input())):
	(L[1], R[1], L[2], R[2], L[3], R[3], L[4], R[4]) = map(int, input().split())
	for i in all_i:
		rng[i] = R[i] - L[i] + 1
	answer = reduce(mul, rng) - 3 * overlap(all_i) + overlap([1, 2]) * overlap([3, 4]) + overlap([2, 3]) * overlap([1, 4])
	for j in range(4):
		answer += overlap([all_i[j], all_i[j - 1], all_i[j - 2]]) * rng[all_i[j - 3]]
		answer -= overlap([all_i[j], all_i[j - 1]]) * rng[all_i[j - 3]] * rng[all_i[j - 2]]
	print(answer % 1000000007)


import sys

def solve(aa, m):

	def overlap(f, t, F, T):
		if t <= F:
			return None
		if T <= f:
			return None
		if f <= F:
			if T <= t:
				return (F, T)
			return (F, t)
		else:
			if T <= t:
				return (f, T)
			return (f, t)
		return None

	def calc(rr, fi, bi):
		total = 1
		for i in fi:
			total *= rr[i][1] - rr[i][0]
			total %= m
		for uu in bi:
			(f, t) = rr[uu[0]]
			for ix in uu[1:]:
				(F, T) = rr[ix]
				ol = overlap(f, t, F, T)
				if ol is None:
					return 0
				(f, t) = ol
			total *= t - f
			total %= m
		return total
	print('aa=%s m=%d' % (aa, m), file=sys.stderr)
	rr = [(aa[i], aa[i + 1] + 1) for i in range(0, len(aa), 2)]
	print('\trr=%s' % (rr,), file=sys.stderr)
	pp = ((1, ((0, 1, 2, 3), tuple())), (-1, ((2, 3), ((0, 1),))), (-1, ((0, 3), ((1, 2),))), (-1, ((0, 1), ((2, 3),))), (-1, ((1, 2), ((3, 0),))), (1, ((3,), ((0, 1, 2),))), (1, (tuple(), ((0, 1), (2, 3)))), (1, ((2,), ((3, 0, 1),))), (1, ((0,), ((1, 2, 3),))), (1, ((1,), ((2, 3, 0),))), (1, (tuple(), ((1, 2), (3, 0)))), (-1, (tuple(), ((0, 1, 2, 3),))), (-1, (tuple(), ((1, 2, 3, 0),))), (-1, (tuple(), ((2, 3, 0, 1),))), (-1, (tuple(), ((3, 0, 1, 2),))), (1, (tuple(), ((0, 1, 2, 3),))))
	total = 0
	for (f, (fi, bi)) in pp:
		delta = calc(rr, fi, bi)
		print('\tfi=%s bi=%s delta=%d' % (fi, bi, delta), file=sys.stderr)
		total += f * delta
		total %= m
	return total
m = pow(10, 9) + 7
t = int(input())
for _ in range(t):
	aa = list(map(int, input().split()))
	print(solve(aa, m))


def solve(l1, r1, l2, r2, l3, r3, l4, r4):
	S = 0
	LL = [0] * 16
	for j in [v for v in range(14) if not v in [11, 13]]:
		L = [[l1, r1], [l2, r2], [l3, r3], [l4, r4]]
		mu = 1
		k = 0
		jj = j
		for i in range(4):
			if j % 2:
				mu *= -1
				L[k] = [max(L[k][0], L[(k + 1) % len(L)][0]), min(L[k][1], L[(k + 1) % len(L)][1])]
				L = L[:(k + 1) % len(L)] + L[(k + 1) % len(L) + 1:]
			else:
				k += 1
			j //= 2
		P = 1
		for x in L:
			P *= max(0, x[1] - x[0] + 1)
		if jj == 7:
			mu = -3
		S += mu * P
	return S % (10 ** 9 + 7)
t = int(input())
for i in range(t):
	(l1, r1, l2, r2, l3, r3, l4, r4) = list(map(int, input().split()))
	print(solve(l1, r1, l2, r2, l3, r3, l4, r4))


M = 10 ** 9 + 7

def powM(b, e):
	if e == 0:
		return 1
	if e == 1:
		return b
	r = powM(b, e >> 1) ** 2
	if e & 1:
		r = r * b
	return r % M

def inter(p, q):
	if p[0] == 0 or q[0] == 0:
		return (0, -1)
	r = (max(p[0], q[0]), min(p[1], q[1]))
	return (0, -1) if r[0] > r[1] else r
for _ in range(int(input())):
	(L1, R1, L2, R2, L3, R3, L4, R4) = map(int, input().split(' '))
	it12 = inter((L1, R1), (L2, R2))
	it23 = inter((L2, R2), (L3, R3))
	it34 = inter((L3, R3), (L4, R4))
	it41 = inter((L4, R4), (L1, R1))
	it123 = inter(it12, it23)
	it234 = inter(it23, it34)
	it341 = inter(it34, it41)
	it412 = inter(it41, it12)
	it1234 = inter(it12, it34)
	print((((R1 - L1 + 1) * (R2 - L2 + 1) * (R3 - L3 + 1) * (R4 - L4 + 1) - ((it12[1] - it12[0] + 1) * (R3 - L3 + 1) * (R4 - L4 + 1) + (it23[1] - it23[0] + 1) * (R4 - L4 + 1) * (R1 - L1 + 1) + (it34[1] - it34[0] + 1) * (R1 - L1 + 1) * (R2 - L2 + 1) + (it41[1] - it41[0] + 1) * (R3 - L3 + 1) * (R2 - L2 + 1)) + ((it12[1] - it12[0] + 1) * (it34[1] - it34[0] + 1) + (it23[1] - it23[0] + 1) * (it41[1] - it41[0] + 1)) + ((it123[1] - it123[0] + 1) * (R4 - L4 + 1) + (it234[1] - it234[0] + 1) * (R1 - L1 + 1) + (it341[1] - it341[0] + 1) * (R2 - L2 + 1) + (it412[1] - it412[0] + 1) * (R3 - L3 + 1)) - (it1234[1] - it1234[0] + 1) * 3) % M + M) % M)


def man(l1, r1, l2, r2, l3, r3, l4, r4):
	S = 0
	for i in [h for h in range(14) if not h in [11, 13]]:
		List = [[l1, r1], [l2, r2], [l3, r3], [l4, r4]]
		m = 1
		k = 0
		ii = i
		for j in range(4):
			if i % 2:
				m *= -1
				List[k] = [max(List[k][0], List[(k + 1) % len(List)][0]), min(List[k][1], List[(k + 1) % len(List)][1])]
				List = List[:(k + 1) % len(List)] + List[(k + 1) % len(List) + 1:]
			else:
				k += 1
			i //= 2
		p = 1
		for x in List:
			p *= max(0, x[1] - x[0] + 1)
		if ii == 7:
			m = -3
		S += m * p
	return S % (10 ** 9 + 7)
T = int(input())
for i in range(T):
	(l1, r1, l2, r2, l3, r3, l4, r4) = list(map(int, input().split()))
	print(man(l1, r1, l2, r2, l3, r3, l4, r4))


from functools import reduce
from operator import mul
L = [0] * 5
R = [0] * 5
rng = [1] * 5
all_i = [1, 2, 3, 4]

def overlap(i_list):
	return max(0, min((R[i] for i in i_list)) - max((L[i] for i in i_list)) + 1)
for _ in range(int(input())):
	(L[1], R[1], L[2], R[2], L[3], R[3], L[4], R[4]) = map(int, input().split())
	for i in all_i:
		rng[i] = R[i] - L[i] + 1
	answer = reduce(mul, rng) - 3 * overlap(all_i) + overlap([1, 2]) * overlap([3, 4]) + overlap([2, 3]) * overlap([1, 4])
	for j in range(4):
		answer += overlap([all_i[j], all_i[j - 1], all_i[j - 2]]) * rng[all_i[j - 3]]
		answer -= overlap([all_i[j], all_i[j - 1]]) * rng[all_i[j - 3]] * rng[all_i[j - 2]]
	print(answer % 1000000007)


MOD = 10 ** 9 + 7

def main():
	T = int(input())
	for _ in range(T):
		(L1, R1, L2, R2, L3, R3, L4, R4) = map(int, input().split())
		(R1, R2, R3, R4) = (R1 + 1, R2 + 1, R3 + 1, R4 + 1)
		Res = (R1 - L1) * (R2 - L2) * (R3 - L3) * (R4 - L4)
		Res -= max(0, min(R1, R2) - max(L1, L2)) * (R3 - L3) * (R4 - L4)
		Res -= max(0, min(R2, R3) - max(L2, L3)) * (R1 - L1) * (R4 - L4)
		Res -= max(0, min(R3, R4) - max(L3, L4)) * (R1 - L1) * (R2 - L2)
		Res -= max(0, min(R4, R1) - max(L4, L1)) * (R2 - L2) * (R3 - L3)
		Res += max(0, min(R1, R2, R3) - max(L1, L2, L3)) * (R4 - L4)
		Res += max(0, min(R1, R2, R4) - max(L1, L2, L4)) * (R3 - L3)
		Res += max(0, min(R1, R3, R4) - max(L1, L3, L4)) * (R2 - L2)
		Res += max(0, min(R2, R3, R4) - max(L2, L3, L4)) * (R1 - L1)
		Res += max(0, min(R1, R2) - max(L1, L2)) * max(0, min(R3, R4) - max(L3, L4))
		Res += max(0, min(R2, R3) - max(L2, L3)) * max(0, min(R4, R1) - max(L4, L1))
		Res -= 3 * max(0, min(R1, R2, R3, R4) - max(L1, L2, L3, L4))
		print(Res % MOD)
main()


def solve(L, R):
	for i in range(len(L)):
		if L[i] > R[i]:
			return 0
	MOD = 10 ** 9 + 7
	ans = 1
	for i in range(len(L)):
		ans = ans * (R[i] - L[i] + 1) % MOD
	return ans
ntest = int(input())
while ntest:
	LR = list(map(int, input().split()))
	L = [LR[0], LR[2], LR[4], LR[6]]
	R = [LR[1], LR[3], LR[5], LR[7]]
	MOD = 10 ** 9 + 7
	for i in range(4):
		if L[i] > R[i]:
			print(0)
			exit()
	ans = solve(L, R)
	for i in range(4):
		(l, r) = ([max(L[i], L[(i + 1) % 4]), L[(i + 2) % 4], L[(i + 3) % 4]], [min(R[i], R[(i + 1) % 4]), R[(i + 2) % 4], R[(i + 3) % 4]])
		ans = (ans + MOD - solve(l, r)) % MOD
	for i in range(4):
		(l, r) = ([max(L[i], L[(i + 1) % 4], L[(i + 2) % 4]), L[(i + 3) % 4]], [min(R[i], R[(i + 1) % 4], R[(i + 2) % 4]), R[(i + 3) % 4]])
		ans = (ans + solve(l, r)) % MOD
	for i in range(2):
		(l, r) = ([max(L[i], L[(i + 1) % 4]), max(L[(i + 2) % 4], L[(i + 3) % 4])], [min(R[i], R[(i + 1) % 4]), min(R[(i + 2) % 4], R[(i + 3) % 4])])
		ans = (ans + solve(l, r)) % MOD
	(l, r) = ([max(L)], [min(R)])
	ans = (ans + MOD - 3 * solve(l, r)) % MOD
	print(ans)
	ntest -= 1


import os, sys, math

def interval_size(a):
	return 0 if a is None else a[1] - a[0] + 1

def intervals_intersection(a):
	res = a[0]
	for b in a[1:]:
		res = (max(res[0], b[0]), min(res[1], b[1]))
		if res[1] < res[0]:
			return None
	return res

def solve(s1, s2, s3, s4):
	MOD = 10 ** 9 + 7

	def ii(*intervals):
		return interval_size(intervals_intersection(intervals))
	(c1, c2, c3, c4) = (interval_size(s1), interval_size(s2), interval_size(s3), interval_size(s4))
	(c12, c23, c34, c41) = (ii(s1, s2), ii(s2, s3), ii(s3, s4), ii(s4, s1))
	(c123, c124, c134, c234) = (ii(s1, s2, s3), ii(s1, s2, s4), ii(s1, s3, s4), ii(s2, s3, s4))
	c1234 = ii(s1, s2, s3, s4)
	failed = 0
	failed += c12 * c3 * c4 + c23 * c1 * c4 + c34 * c1 * c2 + c41 * c2 * c3
	failed -= c123 * c4 + c12 * c34 + c124 * c3 + c234 * c1 + c23 * c41 + c134 * c2
	failed += 4 * c1234
	failed -= c1234
	res = (c1 * c2 * c3 * c4 - failed) % MOD
	if res < 0:
		res += MOD
	return res

def main():
	t = int(sys.stdin.readline())
	for _ in range(t):
		(l1, r1, l2, r2, l3, r3, l4, r4) = list(map(int, sys.stdin.readline().split()))
		print(solve((l1, r1), (l2, r2), (l3, r3), (l4, r4)))
main()


def bforce(W):
	(a, b) = W[0]
	(c, d) = W[1]
	(e, f) = W[2]
	(g, h) = W[3]
	s = 0
	for i in range(a, b + 1):
		for j in range(c, d + 1):
			if i == j:
				continue
			for k in range(e, f + 1):
				if k == j:
					continue
				for l in range(g, h + 1):
					if l == k:
						continue
					if l == i:
						continue
					s += 1
	return s

def cut(a0, b0, a1, b1):
	if a0 <= a1 <= b0 < b1:
		BC = [(a1, b0)]
		BM = [(b0 + 1, b1)]
	elif a0 <= a1 <= b1 <= b0:
		BC = [(a1, b1)]
		BM = []
	elif a1 < a0 <= b0 < b1:
		BC = [(a0, b0)]
		BM = [(a1, a0 - 1), (b0 + 1, b1)]
	elif a1 < a0 <= b1 < b0:
		BC = [(a0, b1)]
		BM = [(a1, a0 - 1)]
	elif b0 < a1:
		BC = []
		BM = [(a1, b1)]
	elif a0 > b1:
		BC = []
		BM = [(a1, b1)]
	elif a1 < a0 <= b0 <= b1:
		BC = [(a0, b1)]
		BM = [(a1, a0 - 1)]
	else:
		print('ERRER', a0, b0, a1, b1)
		BC = []
		BM = []
	return (BC, BM)

def f(W, i, v, A):
	MOD = 10 ** 9 + 7
	if i == 4:
		return v * (A[1] - A[0] + 1) % MOD
	(a0, b0) = A
	(a1, b1) = W[i]
	(BC, BM) = cut(a0, b0, a1, b1)
	a = b0 - a0 + 1
	s = 0
	if len(BC) > 0:
		BCi = BC[0]
		bc = BCi[1] - BCi[0] + 1
		s += f(W, i + 1, ((bc - 1) * v + (a - bc) * v) % MOD, BCi)
	for BMi in BM:
		bmi = BMi[1] - BMi[0] + 1
		s += f(W, i + 1, v * a % MOD, BMi)
	return s % MOD

def g(W, i, v, A, c):
	MOD = 10 ** 9 + 7
	if i == 4:
		r2 = -1
		if c == [1, 1, 1]:
			r2 = A[1] - A[0]
		if not c[-1]:
			a = A[1] - A[0] + 1
			return (v * (a - 1) % MOD, r2)
		else:
			w = W[-1][1] - W[-1][0] + 1
			a = A[1] - A[0] + 1
			v *= a - 1
			if int(v) - v != 0:
				print('ER')
			return (int(v) % MOD, r2)
	(a0, b0) = A
	(a1, b1) = W[i]
	(BC, BM) = cut(a0, b0, a1, b1)
	a = b0 - a0 + 1
	r2 = -1
	s = 0
	if len(BC) > 0:
		BCi = BC[0]
		bc = BCi[1] - BCi[0] + 1
		tot = g(W, i + 1, ((bc - 1) * v + (a - bc) * v) % MOD, BCi, c + [True])
		s += tot[0]
		r2 = max(r2, tot[1])
	for BMi in BM:
		bmi = BMi[1] - BMi[0] + 1
		tot = g(W, i + 1, v * a % MOD, BMi, c + [False])
		s += tot[0]
		r2 = max(r2, tot[1])
	return (s % MOD, r2)

def h(Q):
	s = Q[0][0]
	e = Q[0][1]
	S = {s}
	E = {e}
	for i in range(1, 3):
		if s <= Q[i][0] <= e:
			S.add(Q[i][0])
		if s <= Q[i][0] - 1 <= e:
			E.add(Q[i][0] - 1)
		if s <= Q[i][1] <= e:
			E.add(Q[i][1])
		if s <= Q[i][1] + 1 <= e:
			S.add(Q[i][1] + 1)
	E = list(E)
	S = list(S)
	E.sort()
	S.sort()
	K = []
	if len(S) != len(E):
		print('length error')
	for i in range(min(len(S), len(E))):
		K.append((S[i], E[i]))
	MOD = 10 ** 9 + 7
	s = 0
	r2 = -1
	for K0 in K:
		for K1 in K:
			R = [K0] + Q[1:3] + [K1]
			if K1 == K0:
				sb = g(R, 1, 1, R[0], [])
			else:
				sb = (f(R, 1, 1, R[0]), -1)
			s += sb[0]
			r2 = max(r2, sb[1])
			s = s % MOD
	return (s, r2)

def solve(W):
	MOD = 10 ** 9 + 7
	(a0, b0) = W[0]
	(a1, b1) = W[3]
	(BC, BM) = cut(a0, b0, a1, b1)
	(AC, AM) = cut(a1, b1, a0, b0)
	s = 0
	r2 = 0
	for AMi in AM:
		for BMi in BM:
			Q = [AMi] + W[1:3] + [BMi]
			s += f(Q, 1, 1, Q[0])
			s = s % MOD
		for BCi in BC:
			Q = [AMi] + W[1:3] + [BCi]
			s += f(Q, 1, 1, Q[0])
			s = s % MOD
	for ACi in AC:
		for BCi in BC:
			Q = [ACi] + W[1:3] + [BCi]
			hqa = h(Q)
			hq = hqa[0] % MOD
			if hqa[1] > r2:
				r2 = hqa[1]
			s += hq
			s = s % MOD
		for BMi in BM:
			Q = [ACi] + W[1:3] + [BMi]
			s += f(Q, 1, 1, Q[0])
			s = s % MOD
	return (s + r2) % MOD
T = int(input())
for t0 in range(T):
	(a0, b0, c0, d0, e0, f0, g0, h0) = [int(a) for a in input().split()]
	W = [(a0, b0), (c0, d0), (e0, f0), (g0, h0)]
	sol = solve(W)
	print(sol)


from functools import reduce
MOD = 10 ** 9 + 7

def mul(x, y):
	return x * y % MOD

def add(x, y):
	return (x + y) % MOD

def sub(x, y):
	return (x - y) % MOD

class Interval:

	def __init__(self, left, right):
		self.left = left
		self.right = right

	def __len__(self):
		if self.left is None:
			return 0
		return sub(self.right + 1, self.left)

	def __str__(self):
		if self.left is None:
			return '[]'
		return str([self.left, self.right])

	def intersect(self, other):
		if self.left is None or other.left is None:
			return Interval(None, None)
		if self.right < other.left:
			return Interval(None, None)
		if other.right < self.left:
			return Interval(None, None)
		return Interval(max(self.left, other.left), min(self.right, other.right))

def subsets(s, i=0):
	if i >= len(s):
		return [[]]
	output = subsets(s, i + 1)
	l = len(output)
	for j in range(l):
		output.append([s[i]] + output[j])
	return output

class Disjoint:

	def __init__(self):
		self.nodes = {}
		self.roots = {}

	def makeSet(self, x, interval):
		if x not in self.nodes:
			self.nodes[x] = [None, 1]
			self.roots[x] = interval

	def find(self, x):
		path = []
		while self.nodes[x][0] is not None:
			path.append(x)
			x = self.nodes[x][0]
		xRoot = x
		for x in path:
			self.nodes[x][0] = xRoot
		return xRoot

	def union(self, x, y):
		xRoot = self.find(x)
		yRoot = self.find(y)
		if xRoot == yRoot:
			return
		if self.nodes[xRoot][1] < self.nodes[yRoot][1]:
			(xRoot, yRoot) = (yRoot, xRoot)
		self.nodes[yRoot][0] = xRoot
		self.nodes[xRoot][1] += self.nodes[yRoot][1]
		self.roots[xRoot] = self.roots[xRoot].intersect(self.roots[yRoot])
		del self.roots[yRoot]

def solve(intervals):
	assert len(intervals) == 4
	edgeSubsets = subsets([(i, (i + 1) % 4) for i in range(4)])
	output = 0
	for edges in edgeSubsets:
		disjoint = Disjoint()
		for i in range(4):
			disjoint.makeSet(i, intervals[i])
		for (i, j) in edges:
			disjoint.union(i, j)
		temp = 1 if len(edges) % 2 == 0 else -1
		for q in disjoint.roots.values():
			temp = mul(temp, len(q))
		output = add(output, temp)
	return output

def main():
	t = int(input())
	for i in range(t):
		endpoints = list(map(int, input().strip().split()))
		assert len(endpoints) == 8
		intervals = []
		i = 0
		while i < 8:
			intervals.append(Interval(endpoints[i], endpoints[i + 1]))
			i += 2
		result = solve(intervals)
		print(result)
main()


def solve():

	def find_f(s):
		if fa[s] == -1:
			return s
		fa[s] = find_f(fa[s])
		return fa[s]
	T = int(input())
	mod = 10 ** 9 + 7
	for _ in range(T):
		rl = list(map(int, input().split()))
		res = 1
		for i in range(0, 8, 2):
			res *= rl[i + 1] - rl[i] + 1
		rl = [[rl[i], rl[i + 1]] for i in range(0, 8, 2)]
		for s in range(1, 1 << 4):
			tmp = []
			for i in range(4):
				if s & 1 << i:
					tmp.append(i)
			fa = [-1] * 4
			rlt = [rl[i][:] for i in range(4)]
			for t in tmp:
				l = t
				r = (t + 1) % 4
				fl = find_f(l)
				fr = find_f(r)
				if fl != fr:
					fa[fl] = fr
			for i in range(4):
				fi = find_f(i)
				rlt[fi][0] = max(rlt[fi][0], rl[i][0])
				rlt[fi][1] = min(rlt[fi][1], rl[i][1])
			tres = 1
			for i in range(4):
				if find_f(i) == i:
					tres *= max(0, rlt[i][1] - rlt[i][0] + 1)
			if len(tmp) & 1:
				res -= tres
			else:
				res += tres
		print(res % mod)
solve()


def ic(l, r):
	t = min(r) - max(l)
	return t if t > 0 else 0
n = int(input())
for i in range(n):
	l = [0] * 4
	r = [0] * 4
	(l[0], r[0], l[1], r[1], l[2], r[2], l[3], r[3]) = list(map(int, input().split(' ')))
	for i in range(4):
		r[i] += 1
	tot = 0
	t = [0] * 12
	t[0] = (r[0] - l[0]) * (r[1] - l[1]) * (r[2] - l[2]) * (r[3] - l[3])
	t[1] = ic([l[0], l[1]], [r[0], r[1]]) * (r[2] - l[2]) * (r[3] - l[3])
	t[2] = (r[0] - l[0]) * ic([l[1], l[2]], [r[1], r[2]]) * (r[3] - l[3])
	t[3] = (r[0] - l[0]) * (r[1] - l[1]) * ic([l[2], l[3]], [r[2], r[3]])
	t[4] = ic([l[0], l[3]], [r[0], r[3]]) * (r[2] - l[2]) * (r[1] - l[1])
	print((t[0] - t[1] - t[2] - t[3] - t[4] + ic([l[0], l[1], l[2]], [r[0], r[1], r[2]]) * (r[3] - l[3]) + ic([l[0], l[1], l[3]], [r[0], r[1], r[3]]) * (r[2] - l[2]) + ic([l[0], l[3], l[2]], [r[0], r[3], r[2]]) * (r[1] - l[1]) + ic([l[3], l[1], l[2]], [r[3], r[1], r[2]]) * (r[0] - l[0]) + ic([l[0], l[1]], [r[0], r[1]]) * ic([l[2], l[3]], [r[2], r[3]]) + ic([l[0], l[3]], [r[0], r[3]]) * ic([l[2], l[1]], [r[2], r[1]]) - 3 * ic(l, r)) % 1000000007)


m = 10 ** 9 + 7

def add(a, b):
	return ((a + b) % m + m) % m

def mul(a, b, c=1, d=1):
	return a * b % m * c % m * d % m

def count(a, b=-1, c=-1, d=-1):
	(L, R) = ([l[a]], [r[a]])
	[(L.append(l[i]), R.append(r[i])) for i in [b, c, d] if i > -1]
	return max(0, min(R) - max(L) + 1)
for _ in range(int(input())):
	st = [int(x) for x in input().split()]
	l = [st[x] for x in range(8) if x % 2 == 0]
	r = [st[x] for x in range(8) if x % 2 == 1]
	ret = mul(count(0), count(1), count(2), count(3))
	ret = add(ret, -mul(count(0, 1), count(2), count(3)))
	ret = add(ret, -mul(count(0), count(1, 2), count(3)))
	ret = add(ret, -mul(count(0), count(1), count(2, 3)))
	ret = add(ret, -mul(count(1), count(2), count(3, 0)))
	ret = add(ret, mul(count(0, 1, 2), count(3)))
	ret = add(ret, mul(count(0, 1), count(2, 3)))
	ret = add(ret, mul(count(0, 1, 3), count(2)))
	ret = add(ret, mul(count(0), count(1, 2, 3)))
	ret = add(ret, mul(count(1, 2), count(0, 3)))
	ret = add(ret, mul(count(0, 2, 3), count(1)))
	ret = add(ret, -3 * count(0, 1, 2, 3))
	print(ret)


MOD = 10 ** 9 + 7

class Solution_error(object):

	def solve(self, cipher):
		L = [cipher[2 * i] for i in range(4)]
		R = [cipher[2 * i + 1] for i in range(4)]
		result = 1
		for i in range(4):
			result = result * (R[i] - L[i] + 1) % MOD
		pairs = [(0, 1), (0, 2), (0, 3), (1, 2), (1, 3), (2, 3)]
		for pair in pairs:
			other = max(0, min((R[i] for i in pair)) - max((L[i] for i in pair)) + 1)
			for i in range(4):
				if i not in pair:
					other = other * (R[i] - L[i] + 1) % MOD
			result = (result - other) % MOD
		pairs = [(0, 1, 2), (0, 1, 3), (0, 2, 3), (1, 2, 3)]
		for pair in pairs:
			other = max(0, min((R[i] for i in pair)) - max((L[i] for i in pair)) + 1)
			for i in range(4):
				if i not in pair:
					other = other * (R[i] - L[i] + 1) % MOD
			result = (result + other) % MOD
		result = (result - max(0, min(R) - max(L) + 1)) % MOD
		return result

class Interval(object):

	def __init__(self, l, r):
		self.l = l
		self.r = r

	def card(self):
		if self.is_empty():
			return 0
		return self.r - self.l + 1

	def intersect(self, other):
		if self.is_empty() or other.is_empty():
			return Interval(0, -1)
		l = max(self.l, other.l)
		r = min(self.r, other.r)
		return Interval(l, r)

	def is_empty(self):
		return self.l > self.r

class Solution(object):

	def solve(self, cipher):
		R = [Interval(cipher[2 * i], cipher[2 * i + 1]) for i in range(4)]
		w0 = 0
		w0 += R[0].card() * R[1].card() * R[2].card() * R[3].card()
		w0 %= MOD
		w1 = 0
		for i in range(4):
			w1 += R[i % 4].intersect(R[(i + 1) % 4]).card() * R[(i + 2) % 4].card() * R[(i + 3) % 4].card()
			w1 %= MOD
		w2 = 0
		for i in range(4):
			w2 += R[i % 4].intersect(R[(i + 1) % 4]).intersect(R[(i + 2) % 4]).card() * R[(i + 3) % 4].card()
			w2 %= MOD
		for i in range(2):
			w2 += R[i % 4].intersect(R[(i + 1) % 4]).card() * R[(i + 2) % 4].intersect(R[(i + 3) % 4]).card()
			w2 %= MOD
		w3 = 0
		for i in range(4):
			w3 += R[i % 4].intersect(R[(i + 1) % 4]).intersect(R[(i + 2) % 4]).intersect(R[(i + 3) % 4]).card()
			w3 %= MOD
		w4 = 0
		w4 += R[0].intersect(R[1]).intersect(R[2]).intersect(R[3]).card()
		w4 %= MOD
		return (w0 - w1 + w2 - w3 + w4) % MOD
t = int(input())
for i in range(t):
	s = str(input())
	l = s.strip().split(' ')
	cipher = []
	for x in l:
		cipher.append(int(x))
	solution = Solution()
	s = solution.solve(cipher)
	print(s)


p = int(1000000000.0 + 7)

def intsc(l1, l2):
	if l1 == [] or l2 == []:
		return []
	else:
		a = max(l1[0], l2[0])
		b = min(l1[1], l2[1])
		if b < a:
			return []
		else:
			return [a, b]

def cd(l):
	if l == []:
		return 0
	else:
		return l[1] - l[0] + 1
t = int(input())
for tst in range(t):
	s = input().strip().split()
	w = []
	for i in s:
		w.append(int(i))
	z = {}
	z[0] = [w[0], w[1]]
	z[1] = [w[2], w[3]]
	z[2] = [w[4], w[5]]
	z[3] = [w[6], w[7]]
	comp = 0
	for i in range(4):
		tmp = 1
		L = intsc(z[i], z[(i + 1) % 4])
		j = (i + 2) % 4
		k = (i + 3) % 4
		tmp = tmp * cd(L) % p
		tmp = tmp * cd(z[j]) % p
		tmp = tmp * cd(z[k]) % p
		comp = (comp + tmp) % p
	for i in range(4):
		tmp = 1
		L = intsc(z[i], z[(i + 1) % 4])
		L = intsc(L, z[(i + 2) % 4])
		tmp = cd(L) % p
		tmp = tmp * cd(z[(i + 3) % 4]) % p
		comp = (comp - tmp) % p
	a1 = intsc(z[0], z[1])
	a2 = intsc(z[2], z[3])
	a3 = intsc(z[1], z[2])
	a4 = intsc(z[3], z[0])
	comp = (comp - cd(a1) * cd(a2) % p) % p
	comp = (comp - cd(a3) * cd(a4) % p) % p
	b = intsc(a1, a2)
	comp = (comp + 3 * cd(b)) % p
	tot = 1
	for i in range(4):
		tot *= cd(z[i])
		tot %= p
	tot -= comp
	tot %= p
	print(tot)


p = int(1000000000.0 + 7)

def intsc(l1, l2):
	if l1 == [] or l2 == []:
		return []
	else:
		a = max(l1[0], l2[0])
		b = min(l1[1], l2[1])
		if b < a:
			return []
		else:
			return [a, b]

def cd(l):
	if l == []:
		return 0
	else:
		return l[1] - l[0] + 1
t = int(input())
for tst in range(t):
	s = input().strip().split()
	w = []
	for i in s:
		w.append(int(i))
	z = {}
	z[0] = [w[0], w[1]]
	z[1] = [w[2], w[3]]
	z[2] = [w[4], w[5]]
	z[3] = [w[6], w[7]]
	comp = 0
	for i in range(4):
		tmp = 1
		L = intsc(z[i], z[(i + 1) % 4])
		j = (i + 2) % 4
		k = (i + 3) % 4
		tmp = tmp * cd(L) % p
		tmp = tmp * cd(z[j]) % p
		tmp = tmp * cd(z[k]) % p
		comp = (comp + tmp) % p
	for i in range(4):
		tmp = 1
		L = intsc(z[i], z[(i + 1) % 4])
		L = intsc(L, z[(i + 2) % 4])
		tmp = cd(L) % p
		tmp = tmp * cd(z[(i + 3) % 4]) % p
		comp = (comp - tmp) % p
	a1 = intsc(z[0], z[1])
	a2 = intsc(z[2], z[3])
	a3 = intsc(z[1], z[2])
	a4 = intsc(z[3], z[0])
	comp = (comp - cd(a1) * cd(a2) % p) % p
	comp = (comp - cd(a3) * cd(a4) % p) % p
	b = intsc(a1, a2)
	comp = (comp + 3 * cd(b)) % p
	tot = 1
	for i in range(4):
		tot *= cd(z[i])
		tot %= p
	tot -= comp
	tot %= p
	print(tot)


p = int(1000000000.0 + 7)

def intsc(l1, l2):
	if l1 == [] or l2 == []:
		return []
	else:
		a = max(l1[0], l2[0])
		b = min(l1[1], l2[1])
		if b < a:
			return []
		else:
			return [a, b]

def cd(l):
	if l == []:
		return 0
	else:
		return l[1] - l[0] + 1
t = int(input())
for tst in range(t):
	s = input().strip().split()
	w = []
	for i in s:
		w.append(int(i))
	z = {}
	z[0] = [w[0], w[1]]
	z[1] = [w[2], w[3]]
	z[2] = [w[4], w[5]]
	z[3] = [w[6], w[7]]
	comp = 0
	for i in range(4):
		tmp = 1
		L = intsc(z[i], z[(i + 1) % 4])
		j = (i + 2) % 4
		k = (i + 3) % 4
		tmp = tmp * cd(L) % p
		tmp = tmp * cd(z[j]) % p
		tmp = tmp * cd(z[k]) % p
		comp = (comp + tmp) % p
	for i in range(4):
		tmp = 1
		L = intsc(z[i], z[(i + 1) % 4])
		L = intsc(L, z[(i + 2) % 4])
		tmp = cd(L) % p
		tmp = tmp * cd(z[(i + 3) % 4]) % p
		comp = (comp - tmp) % p
	a1 = intsc(z[0], z[1])
	a2 = intsc(z[2], z[3])
	a3 = intsc(z[1], z[2])
	a4 = intsc(z[3], z[0])
	comp = (comp - cd(a1) * cd(a2) % p) % p
	comp = (comp - cd(a3) * cd(a4) % p) % p
	b = intsc(a1, a2)
	comp = (comp + 3 * cd(b)) % p
	tot = 1
	for i in range(4):
		tot *= cd(z[i])
		tot %= p
	tot -= comp
	tot %= p
	print(tot)


p = int(1000000000.0 + 7)

def intsc(l1, l2):
	if l1 == [] or l2 == []:
		return []
	else:
		a = max(l1[0], l2[0])
		b = min(l1[1], l2[1])
		if b < a:
			return []
		else:
			return [a, b]

def cd(l):
	if l == []:
		return 0
	else:
		return l[1] - l[0] + 1
t = int(input())
for tst in range(t):
	s = input().strip().split()
	w = []
	for i in s:
		w.append(int(i))
	z = {}
	z[0] = [w[0], w[1]]
	z[1] = [w[2], w[3]]
	z[2] = [w[4], w[5]]
	z[3] = [w[6], w[7]]
	comp = 0
	for i in range(4):
		tmp = 1
		L = intsc(z[i], z[(i + 1) % 4])
		j = (i + 2) % 4
		k = (i + 3) % 4
		tmp = tmp * cd(L) % p
		tmp = tmp * cd(z[j]) % p
		tmp = tmp * cd(z[k]) % p
		comp = (comp + tmp) % p
	for i in range(4):
		tmp = 1
		L = intsc(z[i], z[(i + 1) % 4])
		L = intsc(L, z[(i + 2) % 4])
		tmp = cd(L) % p
		tmp = tmp * cd(z[(i + 3) % 4]) % p
		comp = (comp - tmp) % p
	a1 = intsc(z[0], z[1])
	a2 = intsc(z[2], z[3])
	a3 = intsc(z[1], z[2])
	a4 = intsc(z[3], z[0])
	comp = (comp - cd(a1) * cd(a2) % p) % p
	comp = (comp - cd(a3) * cd(a4) % p) % p
	b = intsc(a1, a2)
	comp = (comp + 3 * cd(b)) % p
	tot = 1
	for i in range(4):
		tot *= cd(z[i])
		tot %= p
	tot -= comp
	tot %= p
	print(tot)


p = int(1000000000.0 + 7)

def intsc(l1, l2):
	if l1 == [] or l2 == []:
		return []
	else:
		a = max(l1[0], l2[0])
		b = min(l1[1], l2[1])
		if b < a:
			return []
		else:
			return [a, b]

def cd(l):
	if l == []:
		return 0
	else:
		return l[1] - l[0] + 1
t = int(input())
for tst in range(t):
	s = input().strip().split()
	w = []
	for i in s:
		w.append(int(i))
	z = {}
	z[0] = [w[0], w[1]]
	z[1] = [w[2], w[3]]
	z[2] = [w[4], w[5]]
	z[3] = [w[6], w[7]]
	comp = 0
	for i in range(4):
		tmp = 1
		L = intsc(z[i], z[(i + 1) % 4])
		j = (i + 2) % 4
		k = (i + 3) % 4
		tmp = tmp * cd(L) % p
		tmp = tmp * cd(z[j]) % p
		tmp = tmp * cd(z[k]) % p
		comp = (comp + tmp) % p
	for i in range(4):
		tmp = 1
		L = intsc(z[i], z[(i + 1) % 4])
		L = intsc(L, z[(i + 2) % 4])
		tmp = cd(L) % p
		tmp = tmp * cd(z[(i + 3) % 4]) % p
		comp = (comp - tmp) % p
	a1 = intsc(z[0], z[1])
	a2 = intsc(z[2], z[3])
	a3 = intsc(z[1], z[2])
	a4 = intsc(z[3], z[0])
	comp = (comp - cd(a1) * cd(a2) % p) % p
	comp = (comp - cd(a3) * cd(a4) % p) % p
	b = intsc(a1, a2)
	comp = (comp + 3 * cd(b)) % p
	tot = 1
	for i in range(4):
		tot *= cd(z[i])
		tot %= p
	tot -= comp
	tot %= p
	print(tot)


p = int(1000000000.0 + 7)

def intsc(l1, l2):
	if l1 == [] or l2 == []:
		return []
	else:
		a = max(l1[0], l2[0])
		b = min(l1[1], l2[1])
		if b < a:
			return []
		else:
			return [a, b]

def cd(l):
	if l == []:
		return 0
	else:
		return l[1] - l[0] + 1
t = int(input())
for tst in range(t):
	s = input().strip().split()
	w = []
	for i in s:
		w.append(int(i))
	z = {}
	z[0] = [w[0], w[1]]
	z[1] = [w[2], w[3]]
	z[2] = [w[4], w[5]]
	z[3] = [w[6], w[7]]
	comp = 0
	for i in range(4):
		tmp = 1
		L = intsc(z[i], z[(i + 1) % 4])
		j = (i + 2) % 4
		k = (i + 3) % 4
		tmp = tmp * cd(L) % p
		tmp = tmp * cd(z[j]) % p
		tmp = tmp * cd(z[k]) % p
		comp = (comp + tmp) % p
	for i in range(4):
		tmp = 1
		L = intsc(z[i], z[(i + 1) % 4])
		L = intsc(L, z[(i + 2) % 4])
		tmp = cd(L) % p
		tmp = tmp * cd(z[(i + 3) % 4]) % p
		comp = (comp - tmp) % p
	a1 = intsc(z[0], z[1])
	a2 = intsc(z[2], z[3])
	a3 = intsc(z[1], z[2])
	a4 = intsc(z[3], z[0])
	comp = (comp - cd(a1) * cd(a2) % p) % p
	comp = (comp - cd(a3) * cd(a4) % p) % p
	b = intsc(a1, a2)
	comp = (comp + 3 * cd(b)) % p
	tot = 1
	for i in range(4):
		tot *= cd(z[i])
		tot %= p
	tot -= comp
	tot %= p
	print(tot)


p = int(1000000000.0 + 7)

def intsc(l1, l2):
	if l1 == [] or l2 == []:
		return []
	else:
		a = max(l1[0], l2[0])
		b = min(l1[1], l2[1])
		if b < a:
			return []
		else:
			return [a, b]

def cd(l):
	if l == []:
		return 0
	else:
		return l[1] - l[0] + 1
t = int(input())
for tst in range(t):
	s = input().strip().split()
	w = []
	for i in s:
		w.append(int(i))
	z = {}
	z[0] = [w[0], w[1]]
	z[1] = [w[2], w[3]]
	z[2] = [w[4], w[5]]
	z[3] = [w[6], w[7]]
	comp = 0
	for i in range(4):
		tmp = 1
		L = intsc(z[i], z[(i + 1) % 4])
		j = (i + 2) % 4
		k = (i + 3) % 4
		tmp = tmp * cd(L) % p
		tmp = tmp * cd(z[j]) % p
		tmp = tmp * cd(z[k]) % p
		comp = (comp + tmp) % p
	for i in range(4):
		tmp = 1
		L = intsc(z[i], z[(i + 1) % 4])
		L = intsc(L, z[(i + 2) % 4])
		tmp = cd(L) % p
		tmp = tmp * cd(z[(i + 3) % 4]) % p
		comp = (comp - tmp) % p
	a1 = intsc(z[0], z[1])
	a2 = intsc(z[2], z[3])
	a3 = intsc(z[1], z[2])
	a4 = intsc(z[3], z[0])
	comp = (comp - cd(a1) * cd(a2) % p) % p
	comp = (comp - cd(a3) * cd(a4) % p) % p
	b = intsc(a1, a2)
	comp = (comp + 3 * cd(b)) % p
	tot = 1
	for i in range(4):
		tot *= cd(z[i])
		tot %= p
	tot -= comp
	tot %= p
	print(tot)


p = int(1000000000.0 + 7)

def intsc(l1, l2):
	if l1 == [] or l2 == []:
		return []
	else:
		a = max(l1[0], l2[0])
		b = min(l1[1], l2[1])
		if b < a:
			return []
		else:
			return [a, b]

def cd(l):
	if l == []:
		return 0
	else:
		return l[1] - l[0] + 1
t = int(input())
for tst in range(t):
	s = input().strip().split()
	w = []
	for i in s:
		w.append(int(i))
	z = {}
	z[0] = [w[0], w[1]]
	z[1] = [w[2], w[3]]
	z[2] = [w[4], w[5]]
	z[3] = [w[6], w[7]]
	comp = 0
	for i in range(4):
		tmp = 1
		L = intsc(z[i], z[(i + 1) % 4])
		j = (i + 2) % 4
		k = (i + 3) % 4
		tmp = tmp * cd(L) % p
		tmp = tmp * cd(z[j]) % p
		tmp = tmp * cd(z[k]) % p
		comp = (comp + tmp) % p
	for i in range(4):
		tmp = 1
		L = intsc(z[i], z[(i + 1) % 4])
		L = intsc(L, z[(i + 2) % 4])
		tmp = cd(L) % p
		tmp = tmp * cd(z[(i + 3) % 4]) % p
		comp = (comp - tmp) % p
	a1 = intsc(z[0], z[1])
	a2 = intsc(z[2], z[3])
	a3 = intsc(z[1], z[2])
	a4 = intsc(z[3], z[0])
	comp = (comp - cd(a1) * cd(a2) % p) % p
	comp = (comp - cd(a3) * cd(a4) % p) % p
	b = intsc(a1, a2)
	comp = (comp + 3 * cd(b)) % p
	tot = 1
	for i in range(4):
		tot *= cd(z[i])
		tot %= p
	tot -= comp
	tot %= p
	print(tot)


p = int(1000000000.0 + 7)

def intsc(l1, l2):
	if l1 == [] or l2 == []:
		return []
	else:
		a = max(l1[0], l2[0])
		b = min(l1[1], l2[1])
		if b < a:
			return []
		else:
			return [a, b]

def cd(l):
	if l == []:
		return 0
	else:
		return l[1] - l[0] + 1
t = int(input())
for tst in range(t):
	s = input().strip().split()
	w = []
	for i in s:
		w.append(int(i))
	z = {}
	z[0] = [w[0], w[1]]
	z[1] = [w[2], w[3]]
	z[2] = [w[4], w[5]]
	z[3] = [w[6], w[7]]
	comp = 0
	for i in range(4):
		tmp = 1
		L = intsc(z[i], z[(i + 1) % 4])
		j = (i + 2) % 4
		k = (i + 3) % 4
		tmp = tmp * cd(L) % p
		tmp = tmp * cd(z[j]) % p
		tmp = tmp * cd(z[k]) % p
		comp = (comp + tmp) % p
	for i in range(4):
		tmp = 1
		L = intsc(z[i], z[(i + 1) % 4])
		L = intsc(L, z[(i + 2) % 4])
		tmp = cd(L) % p
		tmp = tmp * cd(z[(i + 3) % 4]) % p
		comp = (comp - tmp) % p
	a1 = intsc(z[0], z[1])
	a2 = intsc(z[2], z[3])
	a3 = intsc(z[1], z[2])
	a4 = intsc(z[3], z[0])
	comp = (comp - cd(a1) * cd(a2) % p) % p
	comp = (comp - cd(a3) * cd(a4) % p) % p
	b = intsc(a1, a2)
	comp = (comp + 3 * cd(b)) % p
	tot = 1
	for i in range(4):
		tot *= cd(z[i])
		tot %= p
	tot -= comp
	tot %= p
	print(tot)


p = int(1000000000.0 + 7)

def intsc(l1, l2):
	if l1 == [] or l2 == []:
		return []
	else:
		a = max(l1[0], l2[0])
		b = min(l1[1], l2[1])
		if b < a:
			return []
		else:
			return [a, b]

def cd(l):
	if l == []:
		return 0
	else:
		return l[1] - l[0] + 1
t = int(input())
for tst in range(t):
	s = input().strip().split()
	w = []
	for i in s:
		w.append(int(i))
	z = {}
	z[0] = [w[0], w[1]]
	z[1] = [w[2], w[3]]
	z[2] = [w[4], w[5]]
	z[3] = [w[6], w[7]]
	comp = 0
	for i in range(4):
		tmp = 1
		L = intsc(z[i], z[(i + 1) % 4])
		j = (i + 2) % 4
		k = (i + 3) % 4
		tmp = tmp * cd(L) % p
		tmp = tmp * cd(z[j]) % p
		tmp = tmp * cd(z[k]) % p
		comp = (comp + tmp) % p
	for i in range(4):
		tmp = 1
		L = intsc(z[i], z[(i + 1) % 4])
		L = intsc(L, z[(i + 2) % 4])
		tmp = cd(L) % p
		tmp = tmp * cd(z[(i + 3) % 4]) % p
		comp = (comp - tmp) % p
	a1 = intsc(z[0], z[1])
	a2 = intsc(z[2], z[3])
	a3 = intsc(z[1], z[2])
	a4 = intsc(z[3], z[0])
	comp = (comp - cd(a1) * cd(a2) % p) % p
	comp = (comp - cd(a3) * cd(a4) % p) % p
	b = intsc(a1, a2)
	comp = (comp + 3 * cd(b)) % p
	tot = 1
	for i in range(4):
		tot *= cd(z[i])
		tot %= p
	tot -= comp
	tot %= p
	print(tot)


p = int(1000000000.0 + 7)

def intsc(l1, l2):
	if l1 == [] or l2 == []:
		return []
	else:
		a = max(l1[0], l2[0])
		b = min(l1[1], l2[1])
		if b < a:
			return []
		else:
			return [a, b]

def cd(l):
	if l == []:
		return 0
	else:
		return l[1] - l[0] + 1
t = int(input())
for tst in range(t):
	s = input().strip().split()
	w = []
	for i in s:
		w.append(int(i))
	z = {}
	z[0] = [w[0], w[1]]
	z[1] = [w[2], w[3]]
	z[2] = [w[4], w[5]]
	z[3] = [w[6], w[7]]
	comp = 0
	for i in range(4):
		tmp = 1
		L = intsc(z[i], z[(i + 1) % 4])
		j = (i + 2) % 4
		k = (i + 3) % 4
		tmp = tmp * cd(L) % p
		tmp = tmp * cd(z[j]) % p
		tmp = tmp * cd(z[k]) % p
		comp = (comp + tmp) % p
	for i in range(4):
		tmp = 1
		L = intsc(z[i], z[(i + 1) % 4])
		L = intsc(L, z[(i + 2) % 4])
		tmp = cd(L) % p
		tmp = tmp * cd(z[(i + 3) % 4]) % p
		comp = (comp - tmp) % p
	a1 = intsc(z[0], z[1])
	a2 = intsc(z[2], z[3])
	a3 = intsc(z[1], z[2])
	a4 = intsc(z[3], z[0])
	comp = (comp - cd(a1) * cd(a2) % p) % p
	comp = (comp - cd(a3) * cd(a4) % p) % p
	b = intsc(a1, a2)
	comp = (comp + 3 * cd(b)) % p
	tot = 1
	for i in range(4):
		tot *= cd(z[i])
		tot %= p
	tot -= comp
	tot %= p
	print(tot)


from collections import Counter
P = 10 ** 9 + 7

def unite(idxs, i, j):
	a = next((k for (k, idx) in enumerate(idxs) if i in idx))
	b = next((k for (k, idx) in enumerate(idxs) if j in idx))
	if a == b:
		return idxs
	return tuple(sorted([idx for (k, idx) in enumerate(idxs) if k not in (a, b)] + [tuple(sorted(idxs[a] + idxs[b]))]))

def solve(ls, rs):
	N = len(ls)

	def calc(e1):
		prod = 1
		for idx in e1:
			left = max((ls[i] for i in idx))
			right = min((rs[i] for i in idx))
			prod *= max(0, right - left + 1)
			prod %= P
		return prod
	e0 = tuple(((i,) for i in range(N)))
	res = Counter([e0])
	for i in range(N):
		j = (i + 1) % N
		new_res = res.copy()
		for (e, c) in res.items():
			new_res[unite(e, i, j)] -= c
		res = new_res
	s = sum((calc(e) * c for (e, c) in res.items()))
	return s % P
T = int(input().strip())
for _ in range(T):
	xs = [int(x) for x in input().split()]
	print(solve(xs[::2], xs[1::2]))


p = int(1000000000.0 + 7)

def intsc(l1, l2):
	if l1 == [] or l2 == []:
		return []
	else:
		a = max(l1[0], l2[0])
		b = min(l1[1], l2[1])
		if b < a:
			return []
		else:
			return [a, b]

def cd(l):
	if l == []:
		return 0
	else:
		return l[1] - l[0] + 1
t = int(input())
for tst in range(t):
	s = input().strip().split()
	w = []
	for i in s:
		w.append(int(i))
	z = {}
	z[0] = [w[0], w[1]]
	z[1] = [w[2], w[3]]
	z[2] = [w[4], w[5]]
	z[3] = [w[6], w[7]]
	comp = 0
	for i in range(4):
		tmp = 1
		L = intsc(z[i], z[(i + 1) % 4])
		j = (i + 2) % 4
		k = (i + 3) % 4
		tmp = tmp * cd(L) % p
		tmp = tmp * cd(z[j]) % p
		tmp = tmp * cd(z[k]) % p
		comp = (comp + tmp) % p
	for i in range(4):
		tmp = 1
		L = intsc(z[i], z[(i + 1) % 4])
		L = intsc(L, z[(i + 2) % 4])
		tmp = cd(L) % p
		tmp = tmp * cd(z[(i + 3) % 4]) % p
		comp = (comp - tmp) % p
	a1 = intsc(z[0], z[1])
	a2 = intsc(z[2], z[3])
	a3 = intsc(z[1], z[2])
	a4 = intsc(z[3], z[0])
	comp = (comp - cd(a1) * cd(a2) % p) % p
	comp = (comp - cd(a3) * cd(a4) % p) % p
	b = intsc(a1, a2)
	comp = (comp + 3 * cd(b)) % p
	tot = 1
	for i in range(4):
		tot *= cd(z[i])
		tot %= p
	tot -= comp
	tot %= p
	print(tot)


p = int(1000000000.0 + 7)

def intsc(l1, l2):
	if l1 == [] or l2 == []:
		return []
	else:
		a = max(l1[0], l2[0])
		b = min(l1[1], l2[1])
		if b < a:
			return []
		else:
			return [a, b]

def cd(l):
	if l == []:
		return 0
	else:
		return l[1] - l[0] + 1
t = int(input())
for tst in range(t):
	s = input().strip().split()
	w = []
	for i in s:
		w.append(int(i))
	z = {}
	z[0] = [w[0], w[1]]
	z[1] = [w[2], w[3]]
	z[2] = [w[4], w[5]]
	z[3] = [w[6], w[7]]
	comp = 0
	for i in range(4):
		tmp = 1
		L = intsc(z[i], z[(i + 1) % 4])
		j = (i + 2) % 4
		k = (i + 3) % 4
		tmp = tmp * cd(L) % p
		tmp = tmp * cd(z[j]) % p
		tmp = tmp * cd(z[k]) % p
		comp = (comp + tmp) % p
	for i in range(4):
		tmp = 1
		L = intsc(z[i], z[(i + 1) % 4])
		L = intsc(L, z[(i + 2) % 4])
		tmp = cd(L) % p
		tmp = tmp * cd(z[(i + 3) % 4]) % p
		comp = (comp - tmp) % p
	a1 = intsc(z[0], z[1])
	a2 = intsc(z[2], z[3])
	a3 = intsc(z[1], z[2])
	a4 = intsc(z[3], z[0])
	comp = (comp - cd(a1) * cd(a2) % p) % p
	comp = (comp - cd(a3) * cd(a4) % p) % p
	b = intsc(a1, a2)
	comp = (comp + 3 * cd(b)) % p
	tot = 1
	for i in range(4):
		tot *= cd(z[i])
		tot %= p
	tot -= comp
	tot %= p
	print(tot)


p = int(1000000000.0 + 7)

def intsc(l1, l2):
	if l1 == [] or l2 == []:
		return []
	else:
		a = max(l1[0], l2[0])
		b = min(l1[1], l2[1])
		if b < a:
			return []
		else:
			return [a, b]

def cd(l):
	if l == []:
		return 0
	else:
		return l[1] - l[0] + 1
t = int(input())
for tst in range(t):
	s = input().strip().split()
	w = []
	for i in s:
		w.append(int(i))
	z = {}
	z[0] = [w[0], w[1]]
	z[1] = [w[2], w[3]]
	z[2] = [w[4], w[5]]
	z[3] = [w[6], w[7]]
	comp = 0
	for i in range(4):
		tmp = 1
		L = intsc(z[i], z[(i + 1) % 4])
		j = (i + 2) % 4
		k = (i + 3) % 4
		tmp = tmp * cd(L) % p
		tmp = tmp * cd(z[j]) % p
		tmp = tmp * cd(z[k]) % p
		comp = (comp + tmp) % p
	for i in range(4):
		tmp = 1
		L = intsc(z[i], z[(i + 1) % 4])
		L = intsc(L, z[(i + 2) % 4])
		tmp = cd(L) % p
		tmp = tmp * cd(z[(i + 3) % 4]) % p
		comp = (comp - tmp) % p
	a1 = intsc(z[0], z[1])
	a2 = intsc(z[2], z[3])
	a3 = intsc(z[1], z[2])
	a4 = intsc(z[3], z[0])
	comp = (comp - cd(a1) * cd(a2) % p) % p
	comp = (comp - cd(a3) * cd(a4) % p) % p
	b = intsc(a1, a2)
	comp = (comp + 3 * cd(b)) % p
	tot = 1
	for i in range(4):
		tot *= cd(z[i])
		tot %= p
	tot -= comp
	tot %= p
	print(tot)


p = int(1000000000.0 + 7)

def intsc(l1, l2):
	if l1 == [] or l2 == []:
		return []
	else:
		a = max(l1[0], l2[0])
		b = min(l1[1], l2[1])
		if b < a:
			return []
		else:
			return [a, b]

def cd(l):
	if l == []:
		return 0
	else:
		return l[1] - l[0] + 1
t = int(input())
for tst in range(t):
	s = input().strip().split()
	w = []
	for i in s:
		w.append(int(i))
	z = {}
	z[0] = [w[0], w[1]]
	z[1] = [w[2], w[3]]
	z[2] = [w[4], w[5]]
	z[3] = [w[6], w[7]]
	comp = 0
	for i in range(4):
		tmp = 1
		L = intsc(z[i], z[(i + 1) % 4])
		j = (i + 2) % 4
		k = (i + 3) % 4
		tmp = tmp * cd(L) % p
		tmp = tmp * cd(z[j]) % p
		tmp = tmp * cd(z[k]) % p
		comp = (comp + tmp) % p
	for i in range(4):
		tmp = 1
		L = intsc(z[i], z[(i + 1) % 4])
		L = intsc(L, z[(i + 2) % 4])
		tmp = cd(L) % p
		tmp = tmp * cd(z[(i + 3) % 4]) % p
		comp = (comp - tmp) % p
	a1 = intsc(z[0], z[1])
	a2 = intsc(z[2], z[3])
	a3 = intsc(z[1], z[2])
	a4 = intsc(z[3], z[0])
	comp = (comp - cd(a1) * cd(a2) % p) % p
	comp = (comp - cd(a3) * cd(a4) % p) % p
	b = intsc(a1, a2)
	comp = (comp + 3 * cd(b)) % p
	tot = 1
	for i in range(4):
		tot *= cd(z[i])
		tot %= p
	tot -= comp
	tot %= p
	print(tot)


p = int(1000000000.0 + 7)

def intsc(l1, l2):
	if l1 == [] or l2 == []:
		return []
	else:
		a = max(l1[0], l2[0])
		b = min(l1[1], l2[1])
		if b < a:
			return []
		else:
			return [a, b]

def cd(l):
	if l == []:
		return 0
	else:
		return l[1] - l[0] + 1
t = int(input())
for tst in range(t):
	s = input().strip().split()
	w = []
	for i in s:
		w.append(int(i))
	z = {}
	z[0] = [w[0], w[1]]
	z[1] = [w[2], w[3]]
	z[2] = [w[4], w[5]]
	z[3] = [w[6], w[7]]
	comp = 0
	for i in range(4):
		tmp = 1
		L = intsc(z[i], z[(i + 1) % 4])
		j = (i + 2) % 4
		k = (i + 3) % 4
		tmp = tmp * cd(L) % p
		tmp = tmp * cd(z[j]) % p
		tmp = tmp * cd(z[k]) % p
		comp = (comp + tmp) % p
	for i in range(4):
		tmp = 1
		L = intsc(z[i], z[(i + 1) % 4])
		L = intsc(L, z[(i + 2) % 4])
		tmp = cd(L) % p
		tmp = tmp * cd(z[(i + 3) % 4]) % p
		comp = (comp - tmp) % p
	a1 = intsc(z[0], z[1])
	a2 = intsc(z[2], z[3])
	a3 = intsc(z[1], z[2])
	a4 = intsc(z[3], z[0])
	comp = (comp - cd(a1) * cd(a2) % p) % p
	comp = (comp - cd(a3) * cd(a4) % p) % p
	b = intsc(a1, a2)
	comp = (comp + 3 * cd(b)) % p
	tot = 1
	for i in range(4):
		tot *= cd(z[i])
		tot %= p
	tot -= comp
	tot %= p
	print(tot)


p = int(1000000000.0 + 7)

def intsc(l1, l2):
	if l1 == [] or l2 == []:
		return []
	else:
		a = max(l1[0], l2[0])
		b = min(l1[1], l2[1])
		if b < a:
			return []
		else:
			return [a, b]

def cd(l):
	if l == []:
		return 0
	else:
		return l[1] - l[0] + 1
t = int(input())
for tst in range(t):
	s = input().strip().split()
	w = []
	for i in s:
		w.append(int(i))
	z = {}
	z[0] = [w[0], w[1]]
	z[1] = [w[2], w[3]]
	z[2] = [w[4], w[5]]
	z[3] = [w[6], w[7]]
	comp = 0
	for i in range(4):
		tmp = 1
		L = intsc(z[i], z[(i + 1) % 4])
		j = (i + 2) % 4
		k = (i + 3) % 4
		tmp = tmp * cd(L) % p
		tmp = tmp * cd(z[j]) % p
		tmp = tmp * cd(z[k]) % p
		comp = (comp + tmp) % p
	for i in range(4):
		tmp = 1
		L = intsc(z[i], z[(i + 1) % 4])
		L = intsc(L, z[(i + 2) % 4])
		tmp = cd(L) % p
		tmp = tmp * cd(z[(i + 3) % 4]) % p
		comp = (comp - tmp) % p
	a1 = intsc(z[0], z[1])
	a2 = intsc(z[2], z[3])
	a3 = intsc(z[1], z[2])
	a4 = intsc(z[3], z[0])
	comp = (comp - cd(a1) * cd(a2) % p) % p
	comp = (comp - cd(a3) * cd(a4) % p) % p
	b = intsc(a1, a2)
	comp = (comp + 3 * cd(b)) % p
	tot = 1
	for i in range(4):
		tot *= cd(z[i])
		tot %= p
	tot -= comp
	tot %= p
	print(tot)


p = int(1000000000.0 + 7)

def intsc(l1, l2):
	if l1 == [] or l2 == []:
		return []
	else:
		a = max(l1[0], l2[0])
		b = min(l1[1], l2[1])
		if b < a:
			return []
		else:
			return [a, b]

def cd(l):
	if l == []:
		return 0
	else:
		return l[1] - l[0] + 1
t = int(input())
for tst in range(t):
	s = input().strip().split()
	w = []
	for i in s:
		w.append(int(i))
	z = {}
	z[0] = [w[0], w[1]]
	z[1] = [w[2], w[3]]
	z[2] = [w[4], w[5]]
	z[3] = [w[6], w[7]]
	comp = 0
	for i in range(4):
		tmp = 1
		L = intsc(z[i], z[(i + 1) % 4])
		j = (i + 2) % 4
		k = (i + 3) % 4
		tmp = tmp * cd(L) % p
		tmp = tmp * cd(z[j]) % p
		tmp = tmp * cd(z[k]) % p
		comp = (comp + tmp) % p
	for i in range(4):
		tmp = 1
		L = intsc(z[i], z[(i + 1) % 4])
		L = intsc(L, z[(i + 2) % 4])
		tmp = cd(L) % p
		tmp = tmp * cd(z[(i + 3) % 4]) % p
		comp = (comp - tmp) % p
	a1 = intsc(z[0], z[1])
	a2 = intsc(z[2], z[3])
	a3 = intsc(z[1], z[2])
	a4 = intsc(z[3], z[0])
	comp = (comp - cd(a1) * cd(a2) % p) % p
	comp = (comp - cd(a3) * cd(a4) % p) % p
	b = intsc(a1, a2)
	comp = (comp + 3 * cd(b)) % p
	tot = 1
	for i in range(4):
		tot *= cd(z[i])
		tot %= p
	tot -= comp
	tot %= p
	print(tot)


p = int(1000000000.0 + 7)

def intsc(l1, l2):
	if l1 == [] or l2 == []:
		return []
	else:
		a = max(l1[0], l2[0])
		b = min(l1[1], l2[1])
		if b < a:
			return []
		else:
			return [a, b]

def cd(l):
	if l == []:
		return 0
	else:
		return l[1] - l[0] + 1
t = int(input())
for tst in range(t):
	s = input().strip().split()
	w = []
	for i in s:
		w.append(int(i))
	z = {}
	z[0] = [w[0], w[1]]
	z[1] = [w[2], w[3]]
	z[2] = [w[4], w[5]]
	z[3] = [w[6], w[7]]
	comp = 0
	for i in range(4):
		tmp = 1
		L = intsc(z[i], z[(i + 1) % 4])
		j = (i + 2) % 4
		k = (i + 3) % 4
		tmp = tmp * cd(L) % p
		tmp = tmp * cd(z[j]) % p
		tmp = tmp * cd(z[k]) % p
		comp = (comp + tmp) % p
	for i in range(4):
		tmp = 1
		L = intsc(z[i], z[(i + 1) % 4])
		L = intsc(L, z[(i + 2) % 4])
		tmp = cd(L) % p
		tmp = tmp * cd(z[(i + 3) % 4]) % p
		comp = (comp - tmp) % p
	a1 = intsc(z[0], z[1])
	a2 = intsc(z[2], z[3])
	a3 = intsc(z[1], z[2])
	a4 = intsc(z[3], z[0])
	comp = (comp - cd(a1) * cd(a2) % p) % p
	comp = (comp - cd(a3) * cd(a4) % p) % p
	b = intsc(a1, a2)
	comp = (comp + 3 * cd(b)) % p
	tot = 1
	for i in range(4):
		tot *= cd(z[i])
		tot %= p
	tot -= comp
	tot %= p
	print(tot)


p = int(1000000000.0 + 7)

def intsc(l1, l2):
	if l1 == [] or l2 == []:
		return []
	else:
		a = max(l1[0], l2[0])
		b = min(l1[1], l2[1])
		if b < a:
			return []
		else:
			return [a, b]

def cd(l):
	if l == []:
		return 0
	else:
		return l[1] - l[0] + 1
t = int(input())
for tst in range(t):
	s = input().strip().split()
	w = []
	for i in s:
		w.append(int(i))
	z = {}
	z[0] = [w[0], w[1]]
	z[1] = [w[2], w[3]]
	z[2] = [w[4], w[5]]
	z[3] = [w[6], w[7]]
	comp = 0
	for i in range(4):
		tmp = 1
		L = intsc(z[i], z[(i + 1) % 4])
		j = (i + 2) % 4
		k = (i + 3) % 4
		tmp = tmp * cd(L) % p
		tmp = tmp * cd(z[j]) % p
		tmp = tmp * cd(z[k]) % p
		comp = (comp + tmp) % p
	for i in range(4):
		tmp = 1
		L = intsc(z[i], z[(i + 1) % 4])
		L = intsc(L, z[(i + 2) % 4])
		tmp = cd(L) % p
		tmp = tmp * cd(z[(i + 3) % 4]) % p
		comp = (comp - tmp) % p
	a1 = intsc(z[0], z[1])
	a2 = intsc(z[2], z[3])
	a3 = intsc(z[1], z[2])
	a4 = intsc(z[3], z[0])
	comp = (comp - cd(a1) * cd(a2) % p) % p
	comp = (comp - cd(a3) * cd(a4) % p) % p
	b = intsc(a1, a2)
	comp = (comp + 3 * cd(b)) % p
	tot = 1
	for i in range(4):
		tot *= cd(z[i])
		tot %= p
	tot -= comp
	tot %= p
	print(tot)


p = int(1000000000.0 + 7)

def intsc(l1, l2):
	if l1 == [] or l2 == []:
		return []
	else:
		a = max(l1[0], l2[0])
		b = min(l1[1], l2[1])
		if b < a:
			return []
		else:
			return [a, b]

def cd(l):
	if l == []:
		return 0
	else:
		return l[1] - l[0] + 1
t = int(input())
for tst in range(t):
	s = input().strip().split()
	w = []
	for i in s:
		w.append(int(i))
	z = {}
	z[0] = [w[0], w[1]]
	z[1] = [w[2], w[3]]
	z[2] = [w[4], w[5]]
	z[3] = [w[6], w[7]]
	comp = 0
	for i in range(4):
		tmp = 1
		L = intsc(z[i], z[(i + 1) % 4])
		j = (i + 2) % 4
		k = (i + 3) % 4
		tmp = tmp * cd(L) % p
		tmp = tmp * cd(z[j]) % p
		tmp = tmp * cd(z[k]) % p
		comp = (comp + tmp) % p
	for i in range(4):
		tmp = 1
		L = intsc(z[i], z[(i + 1) % 4])
		L = intsc(L, z[(i + 2) % 4])
		tmp = cd(L) % p
		tmp = tmp * cd(z[(i + 3) % 4]) % p
		comp = (comp - tmp) % p
	a1 = intsc(z[0], z[1])
	a2 = intsc(z[2], z[3])
	a3 = intsc(z[1], z[2])
	a4 = intsc(z[3], z[0])
	comp = (comp - cd(a1) * cd(a2) % p) % p
	comp = (comp - cd(a3) * cd(a4) % p) % p
	b = intsc(a1, a2)
	comp = (comp + 3 * cd(b)) % p
	tot = 1
	for i in range(4):
		tot *= cd(z[i])
		tot %= p
	tot -= comp
	tot %= p
	print(tot)


p = int(1000000000.0 + 7)

def intsc(l1, l2):
	if l1 == [] or l2 == []:
		return []
	else:
		a = max(l1[0], l2[0])
		b = min(l1[1], l2[1])
		if b < a:
			return []
		else:
			return [a, b]

def cd(l):
	if l == []:
		return 0
	else:
		return l[1] - l[0] + 1
t = int(input())
for tst in range(t):
	s = input().strip().split()
	w = []
	for i in s:
		w.append(int(i))
	z = {}
	z[0] = [w[0], w[1]]
	z[1] = [w[2], w[3]]
	z[2] = [w[4], w[5]]
	z[3] = [w[6], w[7]]
	comp = 0
	for i in range(4):
		tmp = 1
		L = intsc(z[i], z[(i + 1) % 4])
		j = (i + 2) % 4
		k = (i + 3) % 4
		tmp = tmp * cd(L) % p
		tmp = tmp * cd(z[j]) % p
		tmp = tmp * cd(z[k]) % p
		comp = (comp + tmp) % p
	for i in range(4):
		tmp = 1
		L = intsc(z[i], z[(i + 1) % 4])
		L = intsc(L, z[(i + 2) % 4])
		tmp = cd(L) % p
		tmp = tmp * cd(z[(i + 3) % 4]) % p
		comp = (comp - tmp) % p
	a1 = intsc(z[0], z[1])
	a2 = intsc(z[2], z[3])
	a3 = intsc(z[1], z[2])
	a4 = intsc(z[3], z[0])
	comp = (comp - cd(a1) * cd(a2) % p) % p
	comp = (comp - cd(a3) * cd(a4) % p) % p
	b = intsc(a1, a2)
	comp = (comp + 3 * cd(b)) % p
	tot = 1
	for i in range(4):
		tot *= cd(z[i])
		tot %= p
	tot -= comp
	tot %= p
	print(tot)


p = int(1000000000.0 + 7)

def intsc(l1, l2):
	if l1 == [] or l2 == []:
		return []
	else:
		a = max(l1[0], l2[0])
		b = min(l1[1], l2[1])
		if b < a:
			return []
		else:
			return [a, b]

def cd(l):
	if l == []:
		return 0
	else:
		return l[1] - l[0] + 1
t = int(input())
for tst in range(t):
	s = input().strip().split()
	w = []
	for i in s:
		w.append(int(i))
	z = {}
	z[0] = [w[0], w[1]]
	z[1] = [w[2], w[3]]
	z[2] = [w[4], w[5]]
	z[3] = [w[6], w[7]]
	comp = 0
	for i in range(4):
		tmp = 1
		L = intsc(z[i], z[(i + 1) % 4])
		j = (i + 2) % 4
		k = (i + 3) % 4
		tmp = tmp * cd(L) % p
		tmp = tmp * cd(z[j]) % p
		tmp = tmp * cd(z[k]) % p
		comp = (comp + tmp) % p
	for i in range(4):
		tmp = 1
		L = intsc(z[i], z[(i + 1) % 4])
		L = intsc(L, z[(i + 2) % 4])
		tmp = cd(L) % p
		tmp = tmp * cd(z[(i + 3) % 4]) % p
		comp = (comp - tmp) % p
	a1 = intsc(z[0], z[1])
	a2 = intsc(z[2], z[3])
	a3 = intsc(z[1], z[2])
	a4 = intsc(z[3], z[0])
	comp = (comp - cd(a1) * cd(a2) % p) % p
	comp = (comp - cd(a3) * cd(a4) % p) % p
	b = intsc(a1, a2)
	comp = (comp + 3 * cd(b)) % p
	tot = 1
	for i in range(4):
		tot *= cd(z[i])
		tot %= p
	tot -= comp
	tot %= p
	print(tot)


p = int(1000000000.0 + 7)

def intsc(l1, l2):
	if l1 == [] or l2 == []:
		return []
	else:
		a = max(l1[0], l2[0])
		b = min(l1[1], l2[1])
		if b < a:
			return []
		else:
			return [a, b]

def cd(l):
	if l == []:
		return 0
	else:
		return l[1] - l[0] + 1
t = int(input())
for tst in range(t):
	s = input().strip().split()
	w = []
	for i in s:
		w.append(int(i))
	z = {}
	z[0] = [w[0], w[1]]
	z[1] = [w[2], w[3]]
	z[2] = [w[4], w[5]]
	z[3] = [w[6], w[7]]
	comp = 0
	for i in range(4):
		tmp = 1
		L = intsc(z[i], z[(i + 1) % 4])
		j = (i + 2) % 4
		k = (i + 3) % 4
		tmp = tmp * cd(L) % p
		tmp = tmp * cd(z[j]) % p
		tmp = tmp * cd(z[k]) % p
		comp = (comp + tmp) % p
	for i in range(4):
		tmp = 1
		L = intsc(z[i], z[(i + 1) % 4])
		L = intsc(L, z[(i + 2) % 4])
		tmp = cd(L) % p
		tmp = tmp * cd(z[(i + 3) % 4]) % p
		comp = (comp - tmp) % p
	a1 = intsc(z[0], z[1])
	a2 = intsc(z[2], z[3])
	a3 = intsc(z[1], z[2])
	a4 = intsc(z[3], z[0])
	comp = (comp - cd(a1) * cd(a2) % p) % p
	comp = (comp - cd(a3) * cd(a4) % p) % p
	b = intsc(a1, a2)
	comp = (comp + 3 * cd(b)) % p
	tot = 1
	for i in range(4):
		tot *= cd(z[i])
		tot %= p
	tot -= comp
	tot %= p
	print(tot)


p = int(1000000000.0 + 7)

def intsc(l1, l2):
	if l1 == [] or l2 == []:
		return []
	else:
		a = max(l1[0], l2[0])
		b = min(l1[1], l2[1])
		if b < a:
			return []
		else:
			return [a, b]

def cd(l):
	if l == []:
		return 0
	else:
		return l[1] - l[0] + 1
t = int(input())
for tst in range(t):
	s = input().strip().split()
	w = []
	for i in s:
		w.append(int(i))
	z = {}
	z[0] = [w[0], w[1]]
	z[1] = [w[2], w[3]]
	z[2] = [w[4], w[5]]
	z[3] = [w[6], w[7]]
	comp = 0
	for i in range(4):
		tmp = 1
		L = intsc(z[i], z[(i + 1) % 4])
		j = (i + 2) % 4
		k = (i + 3) % 4
		tmp = tmp * cd(L) % p
		tmp = tmp * cd(z[j]) % p
		tmp = tmp * cd(z[k]) % p
		comp = (comp + tmp) % p
	for i in range(4):
		tmp = 1
		L = intsc(z[i], z[(i + 1) % 4])
		L = intsc(L, z[(i + 2) % 4])
		tmp = cd(L) % p
		tmp = tmp * cd(z[(i + 3) % 4]) % p
		comp = (comp - tmp) % p
	a1 = intsc(z[0], z[1])
	a2 = intsc(z[2], z[3])
	a3 = intsc(z[1], z[2])
	a4 = intsc(z[3], z[0])
	comp = (comp - cd(a1) * cd(a2) % p) % p
	comp = (comp - cd(a3) * cd(a4) % p) % p
	b = intsc(a1, a2)
	comp = (comp + 3 * cd(b)) % p
	tot = 1
	for i in range(4):
		tot *= cd(z[i])
		tot %= p
	tot -= comp
	tot %= p
	print(tot)


p = int(1000000000.0 + 7)

def intsc(l1, l2):
	if l1 == [] or l2 == []:
		return []
	else:
		a = max(l1[0], l2[0])
		b = min(l1[1], l2[1])
		if b < a:
			return []
		else:
			return [a, b]

def cd(l):
	if l == []:
		return 0
	else:
		return l[1] - l[0] + 1
t = int(input())
for tst in range(t):
	s = input().strip().split()
	w = []
	for i in s:
		w.append(int(i))
	z = {}
	z[0] = [w[0], w[1]]
	z[1] = [w[2], w[3]]
	z[2] = [w[4], w[5]]
	z[3] = [w[6], w[7]]
	comp = 0
	for i in range(4):
		tmp = 1
		L = intsc(z[i], z[(i + 1) % 4])
		j = (i + 2) % 4
		k = (i + 3) % 4
		tmp = tmp * cd(L) % p
		tmp = tmp * cd(z[j]) % p
		tmp = tmp * cd(z[k]) % p
		comp = (comp + tmp) % p
	for i in range(4):
		tmp = 1
		L = intsc(z[i], z[(i + 1) % 4])
		L = intsc(L, z[(i + 2) % 4])
		tmp = cd(L) % p
		tmp = tmp * cd(z[(i + 3) % 4]) % p
		comp = (comp - tmp) % p
	a1 = intsc(z[0], z[1])
	a2 = intsc(z[2], z[3])
	a3 = intsc(z[1], z[2])
	a4 = intsc(z[3], z[0])
	comp = (comp - cd(a1) * cd(a2) % p) % p
	comp = (comp - cd(a3) * cd(a4) % p) % p
	b = intsc(a1, a2)
	comp = (comp + 3 * cd(b)) % p
	tot = 1
	for i in range(4):
		tot *= cd(z[i])
		tot %= p
	tot -= comp
	tot %= p
	print(tot)


p = int(1000000000.0 + 7)

def intsc(l1, l2):
	if l1 == [] or l2 == []:
		return []
	else:
		a = max(l1[0], l2[0])
		b = min(l1[1], l2[1])
		if b < a:
			return []
		else:
			return [a, b]

def cd(l):
	if l == []:
		return 0
	else:
		return l[1] - l[0] + 1
t = int(input())
for tst in range(t):
	s = input().strip().split()
	w = []
	for i in s:
		w.append(int(i))
	z = {}
	z[0] = [w[0], w[1]]
	z[1] = [w[2], w[3]]
	z[2] = [w[4], w[5]]
	z[3] = [w[6], w[7]]
	comp = 0
	for i in range(4):
		tmp = 1
		L = intsc(z[i], z[(i + 1) % 4])
		j = (i + 2) % 4
		k = (i + 3) % 4
		tmp = tmp * cd(L) % p
		tmp = tmp * cd(z[j]) % p
		tmp = tmp * cd(z[k]) % p
		comp = (comp + tmp) % p
	for i in range(4):
		tmp = 1
		L = intsc(z[i], z[(i + 1) % 4])
		L = intsc(L, z[(i + 2) % 4])
		tmp = cd(L) % p
		tmp = tmp * cd(z[(i + 3) % 4]) % p
		comp = (comp - tmp) % p
	a1 = intsc(z[0], z[1])
	a2 = intsc(z[2], z[3])
	a3 = intsc(z[1], z[2])
	a4 = intsc(z[3], z[0])
	comp = (comp - cd(a1) * cd(a2) % p) % p
	comp = (comp - cd(a3) * cd(a4) % p) % p
	b = intsc(a1, a2)
	comp = (comp + 3 * cd(b)) % p
	tot = 1
	for i in range(4):
		tot *= cd(z[i])
		tot %= p
	tot -= comp
	tot %= p
	print(tot)


p = int(1000000000.0 + 7)

def intsc(l1, l2):
	if l1 == [] or l2 == []:
		return []
	else:
		a = max(l1[0], l2[0])
		b = min(l1[1], l2[1])
		if b < a:
			return []
		else:
			return [a, b]

def cd(l):
	if l == []:
		return 0
	else:
		return l[1] - l[0] + 1
t = int(input())
for tst in range(t):
	s = input().strip().split()
	w = []
	for i in s:
		w.append(int(i))
	z = {}
	z[0] = [w[0], w[1]]
	z[1] = [w[2], w[3]]
	z[2] = [w[4], w[5]]
	z[3] = [w[6], w[7]]
	comp = 0
	for i in range(4):
		tmp = 1
		L = intsc(z[i], z[(i + 1) % 4])
		j = (i + 2) % 4
		k = (i + 3) % 4
		tmp = tmp * cd(L) % p
		tmp = tmp * cd(z[j]) % p
		tmp = tmp * cd(z[k]) % p
		comp = (comp + tmp) % p
	for i in range(4):
		tmp = 1
		L = intsc(z[i], z[(i + 1) % 4])
		L = intsc(L, z[(i + 2) % 4])
		tmp = cd(L) % p
		tmp = tmp * cd(z[(i + 3) % 4]) % p
		comp = (comp - tmp) % p
	a1 = intsc(z[0], z[1])
	a2 = intsc(z[2], z[3])
	a3 = intsc(z[1], z[2])
	a4 = intsc(z[3], z[0])
	comp = (comp - cd(a1) * cd(a2) % p) % p
	comp = (comp - cd(a3) * cd(a4) % p) % p
	b = intsc(a1, a2)
	comp = (comp + 3 * cd(b)) % p
	tot = 1
	for i in range(4):
		tot *= cd(z[i])
		tot %= p
	tot -= comp
	tot %= p
	print(tot)


p = int(1000000000.0 + 7)

def intsc(l1, l2):
	if l1 == [] or l2 == []:
		return []
	else:
		a = max(l1[0], l2[0])
		b = min(l1[1], l2[1])
		if b < a:
			return []
		else:
			return [a, b]

def cd(l):
	if l == []:
		return 0
	else:
		return l[1] - l[0] + 1
t = int(input())
for tst in range(t):
	s = input().strip().split()
	w = []
	for i in s:
		w.append(int(i))
	z = {}
	z[0] = [w[0], w[1]]
	z[1] = [w[2], w[3]]
	z[2] = [w[4], w[5]]
	z[3] = [w[6], w[7]]
	comp = 0
	for i in range(4):
		tmp = 1
		L = intsc(z[i], z[(i + 1) % 4])
		j = (i + 2) % 4
		k = (i + 3) % 4
		tmp = tmp * cd(L) % p
		tmp = tmp * cd(z[j]) % p
		tmp = tmp * cd(z[k]) % p
		comp = (comp + tmp) % p
	for i in range(4):
		tmp = 1
		L = intsc(z[i], z[(i + 1) % 4])
		L = intsc(L, z[(i + 2) % 4])
		tmp = cd(L) % p
		tmp = tmp * cd(z[(i + 3) % 4]) % p
		comp = (comp - tmp) % p
	a1 = intsc(z[0], z[1])
	a2 = intsc(z[2], z[3])
	a3 = intsc(z[1], z[2])
	a4 = intsc(z[3], z[0])
	comp = (comp - cd(a1) * cd(a2) % p) % p
	comp = (comp - cd(a3) * cd(a4) % p) % p
	b = intsc(a1, a2)
	comp = (comp + 3 * cd(b)) % p
	tot = 1
	for i in range(4):
		tot *= cd(z[i])
		tot %= p
	tot -= comp
	tot %= p
	print(tot)


p = int(1000000000.0 + 7)

def intsc(l1, l2):
	if l1 == [] or l2 == []:
		return []
	else:
		a = max(l1[0], l2[0])
		b = min(l1[1], l2[1])
		if b < a:
			return []
		else:
			return [a, b]

def cd(l):
	if l == []:
		return 0
	else:
		return l[1] - l[0] + 1
t = int(input())
for tst in range(t):
	s = input().strip().split()
	w = []
	for i in s:
		w.append(int(i))
	z = {}
	z[0] = [w[0], w[1]]
	z[1] = [w[2], w[3]]
	z[2] = [w[4], w[5]]
	z[3] = [w[6], w[7]]
	comp = 0
	for i in range(4):
		tmp = 1
		L = intsc(z[i], z[(i + 1) % 4])
		j = (i + 2) % 4
		k = (i + 3) % 4
		tmp = tmp * cd(L) % p
		tmp = tmp * cd(z[j]) % p
		tmp = tmp * cd(z[k]) % p
		comp = (comp + tmp) % p
	for i in range(4):
		tmp = 1
		L = intsc(z[i], z[(i + 1) % 4])
		L = intsc(L, z[(i + 2) % 4])
		tmp = cd(L) % p
		tmp = tmp * cd(z[(i + 3) % 4]) % p
		comp = (comp - tmp) % p
	a1 = intsc(z[0], z[1])
	a2 = intsc(z[2], z[3])
	a3 = intsc(z[1], z[2])
	a4 = intsc(z[3], z[0])
	comp = (comp - cd(a1) * cd(a2) % p) % p
	comp = (comp - cd(a3) * cd(a4) % p) % p
	b = intsc(a1, a2)
	comp = (comp + 3 * cd(b)) % p
	tot = 1
	for i in range(4):
		tot *= cd(z[i])
		tot %= p
	tot -= comp
	tot %= p
	print(tot)


p = int(1000000000.0 + 7)

def intsc(l1, l2):
	if l1 == [] or l2 == []:
		return []
	else:
		a = max(l1[0], l2[0])
		b = min(l1[1], l2[1])
		if b < a:
			return []
		else:
			return [a, b]

def cd(l):
	if l == []:
		return 0
	else:
		return l[1] - l[0] + 1
t = int(input())
for tst in range(t):
	s = input().strip().split()
	w = []
	for i in s:
		w.append(int(i))
	z = {}
	z[0] = [w[0], w[1]]
	z[1] = [w[2], w[3]]
	z[2] = [w[4], w[5]]
	z[3] = [w[6], w[7]]
	comp = 0
	for i in range(4):
		tmp = 1
		L = intsc(z[i], z[(i + 1) % 4])
		j = (i + 2) % 4
		k = (i + 3) % 4
		tmp = tmp * cd(L) % p
		tmp = tmp * cd(z[j]) % p
		tmp = tmp * cd(z[k]) % p
		comp = (comp + tmp) % p
	for i in range(4):
		tmp = 1
		L = intsc(z[i], z[(i + 1) % 4])
		L = intsc(L, z[(i + 2) % 4])
		tmp = cd(L) % p
		tmp = tmp * cd(z[(i + 3) % 4]) % p
		comp = (comp - tmp) % p
	a1 = intsc(z[0], z[1])
	a2 = intsc(z[2], z[3])
	a3 = intsc(z[1], z[2])
	a4 = intsc(z[3], z[0])
	comp = (comp - cd(a1) * cd(a2) % p) % p
	comp = (comp - cd(a3) * cd(a4) % p) % p
	b = intsc(a1, a2)
	comp = (comp + 3 * cd(b)) % p
	tot = 1
	for i in range(4):
		tot *= cd(z[i])
		tot %= p
	tot -= comp
	tot %= p
	print(tot)


p = int(1000000000.0 + 7)

def intsc(l1, l2):
	if l1 == [] or l2 == []:
		return []
	else:
		a = max(l1[0], l2[0])
		b = min(l1[1], l2[1])
		if b < a:
			return []
		else:
			return [a, b]

def cd(l):
	if l == []:
		return 0
	else:
		return l[1] - l[0] + 1
t = int(input())
for tst in range(t):
	s = input().strip().split()
	w = []
	for i in s:
		w.append(int(i))
	z = {}
	z[0] = [w[0], w[1]]
	z[1] = [w[2], w[3]]
	z[2] = [w[4], w[5]]
	z[3] = [w[6], w[7]]
	comp = 0
	for i in range(4):
		tmp = 1
		L = intsc(z[i], z[(i + 1) % 4])
		j = (i + 2) % 4
		k = (i + 3) % 4
		tmp = tmp * cd(L) % p
		tmp = tmp * cd(z[j]) % p
		tmp = tmp * cd(z[k]) % p
		comp = (comp + tmp) % p
	for i in range(4):
		tmp = 1
		L = intsc(z[i], z[(i + 1) % 4])
		L = intsc(L, z[(i + 2) % 4])
		tmp = cd(L) % p
		tmp = tmp * cd(z[(i + 3) % 4]) % p
		comp = (comp - tmp) % p
	a1 = intsc(z[0], z[1])
	a2 = intsc(z[2], z[3])
	a3 = intsc(z[1], z[2])
	a4 = intsc(z[3], z[0])
	comp = (comp - cd(a1) * cd(a2) % p) % p
	comp = (comp - cd(a3) * cd(a4) % p) % p
	b = intsc(a1, a2)
	comp = (comp + 3 * cd(b)) % p
	tot = 1
	for i in range(4):
		tot *= cd(z[i])
		tot %= p
	tot -= comp
	tot %= p
	print(tot)


p = int(1000000000.0 + 7)

def intsc(l1, l2):
	if l1 == [] or l2 == []:
		return []
	else:
		a = max(l1[0], l2[0])
		b = min(l1[1], l2[1])
		if b < a:
			return []
		else:
			return [a, b]

def cd(l):
	if l == []:
		return 0
	else:
		return l[1] - l[0] + 1
t = int(input())
for tst in range(t):
	s = input().strip().split()
	w = []
	for i in s:
		w.append(int(i))
	z = {}
	z[0] = [w[0], w[1]]
	z[1] = [w[2], w[3]]
	z[2] = [w[4], w[5]]
	z[3] = [w[6], w[7]]
	comp = 0
	for i in range(4):
		tmp = 1
		L = intsc(z[i], z[(i + 1) % 4])
		j = (i + 2) % 4
		k = (i + 3) % 4
		tmp = tmp * cd(L) % p
		tmp = tmp * cd(z[j]) % p
		tmp = tmp * cd(z[k]) % p
		comp = (comp + tmp) % p
	for i in range(4):
		tmp = 1
		L = intsc(z[i], z[(i + 1) % 4])
		L = intsc(L, z[(i + 2) % 4])
		tmp = cd(L) % p
		tmp = tmp * cd(z[(i + 3) % 4]) % p
		comp = (comp - tmp) % p
	a1 = intsc(z[0], z[1])
	a2 = intsc(z[2], z[3])
	a3 = intsc(z[1], z[2])
	a4 = intsc(z[3], z[0])
	comp = (comp - cd(a1) * cd(a2) % p) % p
	comp = (comp - cd(a3) * cd(a4) % p) % p
	b = intsc(a1, a2)
	comp = (comp + 3 * cd(b)) % p
	tot = 1
	for i in range(4):
		tot *= cd(z[i])
		tot %= p
	tot -= comp
	tot %= p
	print(tot)


p = int(1000000000.0 + 7)

def intsc(l1, l2):
	if l1 == [] or l2 == []:
		return []
	else:
		a = max(l1[0], l2[0])
		b = min(l1[1], l2[1])
		if b < a:
			return []
		else:
			return [a, b]

def cd(l):
	if l == []:
		return 0
	else:
		return l[1] - l[0] + 1
t = int(input())
for tst in range(t):
	s = input().strip().split()
	w = []
	for i in s:
		w.append(int(i))
	z = {}
	z[0] = [w[0], w[1]]
	z[1] = [w[2], w[3]]
	z[2] = [w[4], w[5]]
	z[3] = [w[6], w[7]]
	comp = 0
	for i in range(4):
		tmp = 1
		L = intsc(z[i], z[(i + 1) % 4])
		j = (i + 2) % 4
		k = (i + 3) % 4
		tmp = tmp * cd(L) % p
		tmp = tmp * cd(z[j]) % p
		tmp = tmp * cd(z[k]) % p
		comp = (comp + tmp) % p
	for i in range(4):
		tmp = 1
		L = intsc(z[i], z[(i + 1) % 4])
		L = intsc(L, z[(i + 2) % 4])
		tmp = cd(L) % p
		tmp = tmp * cd(z[(i + 3) % 4]) % p
		comp = (comp - tmp) % p
	a1 = intsc(z[0], z[1])
	a2 = intsc(z[2], z[3])
	a3 = intsc(z[1], z[2])
	a4 = intsc(z[3], z[0])
	comp = (comp - cd(a1) * cd(a2) % p) % p
	comp = (comp - cd(a3) * cd(a4) % p) % p
	b = intsc(a1, a2)
	comp = (comp + 3 * cd(b)) % p
	tot = 1
	for i in range(4):
		tot *= cd(z[i])
		tot %= p
	tot -= comp
	tot %= p
	print(tot)


p = int(1000000000.0 + 7)

def intsc(l1, l2):
	if l1 == [] or l2 == []:
		return []
	else:
		a = max(l1[0], l2[0])
		b = min(l1[1], l2[1])
		if b < a:
			return []
		else:
			return [a, b]

def cd(l):
	if l == []:
		return 0
	else:
		return l[1] - l[0] + 1
t = int(input())
for tst in range(t):
	s = input().strip().split()
	w = []
	for i in s:
		w.append(int(i))
	z = {}
	z[0] = [w[0], w[1]]
	z[1] = [w[2], w[3]]
	z[2] = [w[4], w[5]]
	z[3] = [w[6], w[7]]
	comp = 0
	for i in range(4):
		tmp = 1
		L = intsc(z[i], z[(i + 1) % 4])
		j = (i + 2) % 4
		k = (i + 3) % 4
		tmp = tmp * cd(L) % p
		tmp = tmp * cd(z[j]) % p
		tmp = tmp * cd(z[k]) % p
		comp = (comp + tmp) % p
	for i in range(4):
		tmp = 1
		L = intsc(z[i], z[(i + 1) % 4])
		L = intsc(L, z[(i + 2) % 4])
		tmp = cd(L) % p
		tmp = tmp * cd(z[(i + 3) % 4]) % p
		comp = (comp - tmp) % p
	a1 = intsc(z[0], z[1])
	a2 = intsc(z[2], z[3])
	a3 = intsc(z[1], z[2])
	a4 = intsc(z[3], z[0])
	comp = (comp - cd(a1) * cd(a2) % p) % p
	comp = (comp - cd(a3) * cd(a4) % p) % p
	b = intsc(a1, a2)
	comp = (comp + 3 * cd(b)) % p
	tot = 1
	for i in range(4):
		tot *= cd(z[i])
		tot %= p
	tot -= comp
	tot %= p
	print(tot)