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

You are given an array A consisting of N integers and Q queries. Each query is described by two integers L and R. For each query, output the number of tuples (i, j, k) such that L≤ i< j< k≤ R and A_{i}+A_{j}+A_{k} is an even number.

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

- The first line contains an integer T, the number of test cases. Then the test cases follow.
- The first line of each test case contains two integers N and Q.
- The next line contains N integers A_{1},\ldots,A_{N}.
- Then Q lines follow, each containing two integers L_{i} and R_{i}.

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

For each query, output the number of tuples possible as mentioned in the problem statement.

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

$1 ≤ T ≤ 10^{3}$
$1 ≤ N, Q ≤ 10^{5}$
$0 ≤ A_{i} ≤ 10^{6}$
$1 ≤ L_{i} ≤ R_{i} ≤ N$
- The sum of $N$ over all test cases does not exceed $10^{6}$.
- The sum of $Q$ over all test cases does not exceed $10^{5}$

----- Sample Input 1 ------ 
1
6 3
1 2 3 4 5 6
1 3
2 5
1 6
----- Sample Output 1 ------ 
1
2
10
----- explanation 1 ------ 
- For the first query, we can choose $(1, 2, 3)$ since $A_{1} + A_{2} + A_{3} = 6$ is an even 
number.
- For the second query, we can choose $(2, 3, 5)$ since $A_{2} + A_{3} + A_{5} = 10$ is even, and $(3, 4, 5)$ since $A_{3} + A_{4} + A_{5} = 12$ is even.

Difficulty: HARD
Tags: Mathematics

Range queries
Skill types: Range queries

Starter code:

Solutions:
for _ in range(int(input())):
	(N, Q) = list(map(int, input().split()))
	A = list(map(int, input().split()))
	even = [0] * N
	odd = [0] * N
	for i in range(N):
		even[i] += even[max(i - 1, 0)]
		odd[i] += odd[max(i - 1, 0)]
		if i != N - 1:
			if A[i] % 2:
				odd[i + 1] += 1
			else:
				even[i + 1] += 1
	for i in range(Q):
		(L, R) = list(map(int, input().split()))
		L -= 1
		R -= 1
		num_evens = even[R] - even[L] + 1 * (not A[R] % 2)
		num_odds = odd[R] - odd[L] + 1 * (A[R] % 2)
		choose2 = num_odds * (num_odds - 1) // 2 * num_evens
		choose3 = num_evens * (num_evens - 1) * (num_evens - 2) // 6
		print(choose2 + choose3)


for i in range(int(input())):
	(x, y) = map(int, input().split())
	a = list(map(int, input().split()))
	s = []
	c = 0
	for i in a:
		if i % 2 == 0:
			c += 1
			s.append(c)
		else:
			s.append(c)
	for i in range(y):
		(b, c) = map(int, input().split())
		e = s[c - 1] - s[b - 1]
		if a[b - 1] % 2 == 0:
			e += 1
		o = c - b + 1 - e
		z = e * int(o * (o - 1) / 2) + int(e * (e - 1) * (e - 2) / 6)
		print(z)


from sys import stdin, stdout
test = int(stdin.readline().rstrip())
while test > 0:
	(n, q) = map(int, stdin.readline().rstrip().split())
	array = list(map(int, stdin.readline().rstrip().split()))
	lst = []
	c = 0
	for i in range(len(array)):
		if array[i] % 2 == 0:
			c += 1
		lst.append(c)
	while q > 0:
		(a, b) = map(int, stdin.readline().rstrip().split())
		c = lst[b - 1] - lst[a - 1]
		if array[a - 1] % 2 == 0:
			c += 1
		o = b - a + 1 - c
		x = o * (o - 1) // 2 * c
		y = c * (c - 1) * (c - 2) // 6
		print(x + y)
		q -= 1
	test -= 1


from math import *
import sys

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

def nc3(x):
	if x < 3:
		return 0
	return x * (x - 1) * (x - 2) // 6

def nc2(x):
	if x < 2:
		return 0
	return x * (x - 1) // 2
for _ in range(int(input())):
	(n, q) = list(map(int, input().split()))
	l = list(map(int, input().split()))
	even = [0] * n
	odd = [0] * n
	for i in range(n):
		if l[i] % 2 == 0:
			even[i] = even[i - 1] + 1
			odd[i] = odd[i - 1]
		else:
			odd[i] = odd[i - 1] + 1
			even[i] = even[i - 1]
	for i in range(q):
		(l, r) = list(map(int, input().split()))
		l -= 1
		r -= 1
		if l == 0:
			even_c = even[r]
			odd_c = odd[r]
		else:
			even_c = even[r] - even[l - 1]
			odd_c = odd[r] - odd[l - 1]
		ans = nc3(even_c) + even_c * nc2(odd_c)
		print(ans)


ans = ''

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

def nC2(n):
	return int(n * (n - 1) / 2)
for _ in range(int(input())):
	(n, q) = list(map(int, input().split()))
	a = list(map(int, input().split()))
	pre = [0] * n
	pre[0] = 1 if a[0] % 2 == 0 else 0
	for i in range(1, n):
		if a[i] % 2 == 0:
			pre[i] += 1
		pre[i] += pre[i - 1]
	for i in range(q):
		(l, r) = list(map(int, input().split()))
		even = pre[r - 1] - pre[l - 1] + (1 if a[l - 1] % 2 == 0 else 0)
		odd = r - l + 1 - even
		res = nC3(even) + nC2(odd) * even
		ans += str(res) + '\n'
print(ans)


for _ in range(int(input())):
	(n, q) = map(int, input().split())
	x = list(map(int, input().split()))
	if x[0] % 2 == 0:
		xd = [1]
	else:
		xd = [0]
	for i in range(1, n):
		if x[i] % 2 == 0:
			xd += [1]
		else:
			xd += [0]
		xd[i] += xd[i - 1]
	for _ in range(q):
		(l, r) = map(int, input().split())
		if r - l < 2:
			print(0)
		else:
			e = xd[r - 1] - xd[l - 1]
			if x[l - 1] % 2 == 0:
				e += 1
			o = r - l + 1 - e
			ans = 0
			if o >= 2 and e >= 1:
				ans += o * (o - 1) // 2 * e
			if e >= 3:
				ans += e * (e - 1) * (e - 2) // 6
			print(ans)


for _ in range(int(input())):
	(n, q) = map(int, input().split())
	a = list(map(int, input().split()))
	ha = [0] * (len(a) + 1)
	for i in range(0, len(a)):
		if a[i] % 2 == 0:
			ha[i + 1] = ha[i] + 1
		else:
			ha[i + 1] = ha[i]
	for x in range(q):
		(l, r) = map(int, input().split())
		even = ha[r] - ha[l - 1]
		odd = r - l + 1 - even
		ans = even * (even - 1) * (even - 2) / 6 + odd * (odd - 1) / 2 * even
		print(int(ans))


try:
	for i in range(int(input())):
		(n, q) = map(int, input().split())
		a = list(map(int, input().split()))
		z = [0] * (n + 1)
		for j in range(n):
			if a[j] % 2 == 0:
				z[j + 1] = z[j] + 1
			else:
				z[j + 1] = z[j]
		for i in range(q):
			(l, r) = map(int, input().split())
			e = z[r] - z[l - 1]
			o = r - l + 1 - e
			c_ev = e * (e - 1) * (e - 2) // 6
			c_od = o * (o - 1) * e // 2
			print(c_od + c_ev)
except:
	pass


for _ in range(int(input())):
	(n, q) = [int(x) for x in input().split()]
	a = [int(x) for x in input().split()]
	pre = [0] * (n + 1)
	for i in range(n):
		pre[i + 1] = pre[i]
		if a[i] & 1:
			pre[i + 1] += 1
	for _ in range(q):
		(l, r) = [int(x) for x in input().split()]
		odds = pre[r] - pre[l - 1]
		evens = r - l + 1 - odds
		if evens >= 3:
			even_answer = evens * (evens - 1) * (evens - 2) // 6
		else:
			even_answer = 0
		if odds >= 2:
			lal = odds - 1
			odd_answer = lal * (lal + 1) // 2 * evens
		else:
			odd_answer = 0
		print(even_answer + odd_answer)


import math
for t in range(int(input())):
	(n, q) = map(int, input().split())
	a = [int(x) for x in input().split()]
	e = [0] * (n + 1)
	o = [0] * (n + 1)
	c = 0
	d = 0
	for i in range(n):
		if a[i] % 2 == 0:
			c += 1
		e[i + 1] = c
		if a[i] % 2 != 0:
			d += 1
		o[i + 1] = d
	for i in range(q):
		(l, r) = map(int, input().split())
		e1 = 0
		c = 0
		b = e[r] - e[l - 1]
		if b < 3:
			e1 = 0
		else:
			x = b * (b - 1) * (b - 2)
			c += x // 6
		d = o[r] - o[l - 1]
		if d > 1 and b > 0:
			x = d * (d - 1)
			p = x * b // 2
			c += p
		print(c)


t = int(input())
for i in range(t):
	(N, Q) = input().split()
	n = int(N)
	q = int(Q)
	arr = [int(i) for i in input().split()]
	l = [[0, 0]]
	for i in range(n):
		a = l[i]
		x = a[0]
		y = a[1]
		if arr[i] % 2 == 0:
			l.append([x + 1, y])
		else:
			l.append([x, y + 1])
	for i in range(q):
		(A, B) = input().split()
		a = int(A)
		b = int(B)
		p = l[a - 1][0]
		q = l[a - 1][1]
		r = l[b][0]
		s = l[b][1]
		even = abs(p - r)
		odd = abs(q - s)
		if even == 0:
			print(0)
		else:
			ans = int((odd - 1) * odd / 2) * even
			if even >= 3:
				ans += int(even * (even - 1) * (even - 2) / 6)
			print(ans)


def binomialCoefficient(n, k):
	if k > n - k:
		k = n - k
	res = 1
	for i in range(k):
		res = res * (n - i)
		res = res // (i + 1)
	return res
t = int(input())
for _ in range(t):
	(n, q) = map(int, input().split())
	arr = list(map(int, input().split()))
	queries = []
	for _ in range(q):
		(l, r) = map(int, input().split())
		queries.append([l, r])
	even = [0] * len(arr)
	odd = [0] * len(arr)
	n = len(arr)
	for i in range(len(arr)):
		if arr[i] % 2 == 0:
			even[i] = 1
		else:
			odd[i] = 1
	prefixSum_odd = [0 for i in range(n + 1)]
	prefixSum_odd[0] = odd[0]
	for i in range(1, n):
		prefixSum_odd[i] = prefixSum_odd[i - 1] + odd[i]
	prefixSum_even = [0 for i in range(n + 1)]
	prefixSum_even[0] = even[0]
	for i in range(1, n):
		prefixSum_even[i] = prefixSum_even[i - 1] + even[i]
	for query in queries:
		a = prefixSum_even[query[1] - 1] - prefixSum_even[query[0] - 2]
		b = prefixSum_odd[query[1] - 1] - prefixSum_odd[query[0] - 2]
		term1 = 0
		term2 = 0
		term3 = 0
		if a >= 3:
			term1 = binomialCoefficient(a, 3)
		if a >= 1:
			term2 = binomialCoefficient(a, 1)
		if b >= 2:
			term3 = binomialCoefficient(b, 2)
		result = term1 + term2 * term3
		print(result)


for t in range(int(input())):
	(n, q) = map(int, input().split())
	a = list(map(int, input().split()))
	o = [0]
	e = [0]
	for i in a:
		if i % 2 == 0:
			e.append(e[-1] + 1)
			o.append(o[-1])
		else:
			o.append(o[-1] + 1)
			e.append(e[-1])
	for x in range(q):
		(l, r) = map(int, input().split())
		ne = e[r] - e[l - 1]
		no = o[r] - o[l - 1]
		ans = ne * (ne - 1) * (ne - 2) // 6
		ans += ne * no * (no - 1) // 2
		print(ans)


t = int(input())
for _ in range(t):
	(n, q) = list(map(int, input().split()))
	arr = list(map(int, input().split()))
	arr = [item & 1 for item in arr]
	cum = 0
	for i in range(len(arr)):
		cum += arr[i]
		arr[i] = cum
	for i in range(q):
		(l, r) = list(map(int, input().split()))
		tot = r - l + 1
		if l - 1 == 0:
			odd = arr[r - 1]
		else:
			odd = arr[r - 1] - arr[l - 2]
		even = tot - odd
		k1 = odd * (odd - 1) // 2
		k2 = even * (even - 1) * (even - 2) // 6
		print(even * k1 + k2)


def A():
	for _ in range(int(input())):
		(R1, W1, C1) = [int(x) for x in input().split()]
		(R2, W2, C2) = [int(x) for x in input().split()]
		(A, B) = (0, 0)
		if R1 > R2:
			A += 1
		else:
			B += 1
		if W1 > W2:
			A += 1
		else:
			B += 1
		if C1 > C2:
			A += 1
		else:
			B += 1
		print('A' if A > B else 'B')

def B():
	for _ in range(int(input())):
		(X, Y) = [int(x) for x in input().split()]
		s = X + Y
		if s >= 6:
			print(0)
		else:
			print((6 - s) / 6)

def C():
	for _ in range(int(input())):
		(N, M, L) = [int(x) for x in input().split()]
		A = [[int(x) for x in input().split()] for i in range(M)]
		S = [int(x) for x in input().split()]
		colors = [0] * (N + 1)
		for i in range(M):
			for color in A[i][1:]:
				colors[color] = i
		segments = 1
		for i in range(1, L):
			if colors[S[i - 1]] != colors[S[i]]:
				segments += 1
		print(segments)

def D():

	def calc(odd, even):
		ans = even * (even - 1) * (even - 2) // 6 if even > 2 else 0
		ans += even * odd * (odd - 1) // 2 if odd > 1 else 0
		return ans
	for _ in range(int(input())):
		(N, Q) = [int(x) for x in input().split()]
		A = [int(x) for x in input().split()]
		LR = [[int(x) for x in input().split()] for i in range(Q)]
		(even, odd) = ([0] * N, [0] * N)
		if A[0] % 2 is 0:
			even[0] += 1
		else:
			odd[0] += 1
		for (i, a) in enumerate(A[1:], start=1):
			if a % 2 is 0:
				even[i] = even[i - 1] + 1
				odd[i] = odd[i - 1]
			else:
				even[i] = even[i - 1]
				odd[i] = odd[i - 1] + 1
		for i in range(Q):
			(L, R) = (LR[i][0] - 1, LR[i][1] - 1)
			if L is 0:
				print(calc(odd[R], even[R]))
			else:
				print(calc(odd[R] - odd[L - 1], even[R] - even[L - 1]))
D()


from math import factorial
test_case = int(input())
for i in range(test_case):
	(n, q) = map(int, input().split())
	n_arr = list(map(int, input().split()))
	even = [0] * (n + 1)
	for j in range(0, n):
		if n_arr[j] % 2 == 0:
			even[j + 1] = even[j] + 1
		else:
			even[j + 1] = even[j]
	for j in range(0, q):
		(l, r) = map(int, input().split())
		nEven = even[r] - even[l - 1]
		nOdd = r - l + 1 - nEven
		alleven = nEven * (nEven - 1) * (nEven - 2) // 6
		oneeven = nOdd * (nOdd - 1) // 2 * nEven
		print(alleven + oneeven)


for t in range(int(input())):
	(n, q) = list(map(int, input().split()))
	lst = list(map(int, input().split()))
	even_odd_list = [0 for i in range(n + 1)]
	for i in range(1, len(even_odd_list)):
		if lst[i - 1] % 2 == 0:
			even_odd_list[i] += 1 + even_odd_list[i - 1]
		else:
			even_odd_list[i] = even_odd_list[i - 1]
	for i in range(q):
		lr = list(map(int, input().split()))
		l = lr[0]
		r = lr[1]
		TE = even_odd_list[r] - even_odd_list[l - 1]
		TO = r - l + 1 - TE
		one = TE * (TE - 1) * (TE - 2) // 6
		two = TO * (TO - 1) // 2 * TE
		print(one + two)


def fact(a, b):
	if a < b:
		return 0
	elif a == b:
		return 1
	elif b == 1:
		return a
	elif b == 2:
		return a * (a - 1) / 2
	else:
		return a * (a - 1) * (a - 2) / 6
for _ in range(int(input())):
	(n, q) = map(int, input().split())
	l = list(map(int, input().split()))
	arr = []
	eve = 0
	odd = 0
	for i in range(len(l)):
		k = []
		if l[i] % 2 == 0:
			eve += 1
		else:
			odd += 1
		k.append(eve)
		k.append(odd)
		arr.append(k)
	for i in range(q):
		(first, last) = map(int, input().split())
		first -= 2
		last -= 1
		if first == -1:
			f_eve = arr[last][0]
			f_odd = arr[last][1]
		else:
			f_eve = arr[last][0] - arr[first][0]
			f_odd = arr[last][1] - arr[first][1]
		if f_eve < 1:
			print(0)
		elif f_odd < 2 and f_eve < 3:
			print(0)
		else:
			z = fact(f_eve, 3) + fact(f_eve, 1) * fact(f_odd, 2)
			print(int(z))


def checkeven(n):
	if n % 2 == 0:
		return 1
	else:
		return 0
t = int(input())
for i in range(t):
	ip = input()
	(sn, sq) = ip.split(' ')
	(n, q) = (int(sn), int(sq))
	arr = [0] * (n + 1)
	istrip = input()
	strip = []
	strip = istrip.split(' ')
	strip = list(map(int, strip))
	strip.insert(0, 0)
	c = 0
	c = checkeven(strip[1])
	arr[1] = c
	for j in range(2, n + 1):
		c += checkeven(strip[j])
		arr[j] = c
	for j in range(q):
		ip = input()
		(sl, sr) = ip.split(' ')
		(l, r) = (int(sl), int(sr))
		even = arr[r] - arr[l - 1]
		odd = r - l + 1 - even
		ceven = int(even * (even - 1) * (even - 2) / 6)
		codd = int(odd * (odd - 1) / 2 * even)
		out = ceven + codd
		print(out)


t = int(input())

def f(x):
	if int(x) % 2 == 0:
		return 0
	else:
		return 1
for i in range(t):
	(n, q) = map(int, input().split())
	arr = list(map(f, input().split()))
	cumul = None
	arr2 = [0]
	for j in range(len(arr)):
		temp = arr[j]
		if cumul is None:
			cumul = temp
		else:
			cumul = cumul + temp
		arr2.append(cumul)
	for j in range(q):
		(l, r) = map(int, input().split())
		nodd = arr2[r] - arr2[l - 1]
		neven = r - l + 1 - nodd
		res = neven * (neven - 1) * (neven - 2) / 6
		res += nodd * (nodd - 1) * neven / 2
		res = int(res) if res > 0 else 0
		print(res)


def NC3(x):
	if x < 3:
		return 0
	elif x == 3:
		return 1
	else:
		return x * (x - 1) * (x - 2) // 6

def NC2(x):
	if x < 2:
		return 0
	elif x == 2:
		return 1
	else:
		return x * (x - 1) // 2
for _ in range(int(input())):
	(n, q) = map(int, input().split())
	arr = list(map(int, input().split()))
	even = [0]
	for i in range(n):
		if arr[i] % 2 == 0:
			even.append(even[i] + 1)
		else:
			even.append(even[i])
	for i in range(q):
		(q1, q2) = map(int, input().split())
		e = even[q2] - even[q1 - 1]
		o = q2 - q1 + 1 - e
		print(NC3(e) + NC2(o) * e)


for _ in range(int(input())):
	(n, k) = list(map(int, input().split()))
	lst = list(map(int, input().split()))
	arr = [0] * (n + 1)
	for j in range(n):
		if lst[j] % 2 == 0:
			arr[j + 1] = arr[j] + 1
		else:
			arr[j + 1] = arr[j]
	for i in range(k):
		(l, r) = list(map(int, input().split()))
		even = arr[r] - arr[l - 1]
		odd = r - l + 1 - even
		t = even * (even - 1) * (even - 2) // 6
		v = even * odd * (odd - 1) // 2
		print(t + v)


import operator as op
from functools import reduce

def ncr(n, r):
	if n < r:
		return 0
	elif n == r:
		return 1
	r = min(r, n - r)
	numer = reduce(op.mul, range(n, n - r, -1), 1)
	denom = reduce(op.mul, range(1, r + 1), 1)
	return numer // denom
t = int(input())
for tc in range(t):
	(n, q) = map(int, input().split())
	nums = list(map(int, input().split()))
	odds = [0]
	for i in range(n):
		if nums[i] & 1 == 1:
			odds.append(odds[-1] + 1)
		else:
			odds.append(odds[-1])
	for qry in range(q):
		(l, r) = map(int, input().split())
		o = odds[r] - odds[l - 1]
		e = r - l + 1 - o
		pairs = ncr(o, 2) * e + ncr(e, 3)
		print(pairs)


for _ in range(int(input())):
	(n, q) = map(int, input().split())
	ar = list(map(int, input().split()))
	op = ar[:]
	ep = ar[:]
	if ar[0] % 2 == 0:
		ep[0] = 1
		op[0] = 0
	else:
		op[0] = 1
		ep[0] = 0
	for i in range(1, n):
		if ar[i] % 2 == 0:
			ep[i] = ep[i - 1] + 1
			op[i] = op[i - 1]
		else:
			op[i] = op[i - 1] + 1
			ep[i] = ep[i - 1]
	ep.insert(0, 0)
	op.insert(0, 0)
	for i in range(q):
		(l, r) = map(int, input().split())
		nop = op[r] - op[l - 1]
		noe = ep[r] - ep[l - 1]
		ctr = 0
		if noe >= 3:
			ctr += noe * (noe - 1) * (noe - 2) // 6
		if nop >= 2 and noe >= 1:
			ctr += noe * (nop * (nop - 1) // 2)
		print(ctr)


t = int(input())
for i in range(t):
	(n, q) = map(int, input().split())
	l = list(map(int, input().split()))
	arr = list()
	arr.append(0)
	for k in range(n):
		arr.append(0)
	for k in range(n):
		if l[k] % 2 == 0:
			arr[k + 1] = arr[k] + 1
		else:
			arr[k + 1] = arr[k]
	for j in range(q):
		(ld, rd) = map(int, input().split())
		count_even = arr[rd] - arr[ld - 1]
		count_odd = rd - ld + 1 - count_even
		print(count_even * (count_even - 1) * (count_even - 2) // 6 + count_odd * (count_odd - 1) // 2 * count_even)


def NC3(x):
	if x < 3:
		return 0
	elif x == 3:
		return 1
	else:
		return x * (x - 1) * (x - 2) // 6

def NC2(x):
	if x < 2:
		return 0
	elif x == 2:
		return 1
	else:
		return x * (x - 1) // 2
t = int(input())
while t:
	t -= 1
	(n, q) = map(int, input().split())
	a = list(map(int, input().split()))
	odds = [0]
	evens = [0]
	for i in a:
		if i & 1:
			odds.append(odds[-1] + 1)
			evens.append(evens[-1])
		else:
			odds.append(odds[-1])
			evens.append(evens[-1] + 1)
	for i in range(q):
		query = list(map(int, input().split()))
		even = evens[query[1]] - evens[query[0] - 1]
		odd = odds[query[1]] - odds[query[0] - 1]
		sol = NC3(even) + NC2(odd) * even
		print(sol)


import sys, collections, math, itertools, random, bisect, string
INF = sys.maxsize

def intp():
	return map(int, sys.stdin.readline().strip().split())

def ls():
	return list(map(int, sys.stdin.readline().strip().split()))

def input():
	return sys.stdin.readline().strip()
mod = 1000000007
for _ in range(int(input())):
	(x, y) = intp()
	lst = ls()
	(pe, po) = ([0] * x, [0] * x)
	pe[0] = int(lst[0] % 2 == 0)
	po[0] = lst[0] % 2
	for i in range(1, x):
		pe[i] = pe[i - 1] + int(lst[i] % 2 == 0)
		po[i] = po[i - 1] + lst[i] % 2
	for i in range(y):
		(l, r) = intp()
		l -= 1
		r -= 1
		oc = po[r] - (po[l - 1] if l > 0 else 0)
		ec = pe[r] - (pe[l - 1] if l > 0 else 0)
		ans = ec * (ec - 1) * (ec - 2) // 6 + ec * oc * (oc - 1) // 2
		print(ans)


t = int(input())
while t:
	(n, q) = map(int, input().split())
	a = [int(x) for x in input().split()]
	final = [x for x in range(len(a))]
	j = 0
	for i in a:
		if j == 0:
			final[j] = i % 2
		else:
			final[j] = final[j - 1] + i % 2
		j += 1
	for _ in range(q):
		(l, r) = map(int, input().split())
		fir = l - 1
		las = r - 1
		even = odd = 0
		if fir == 0:
			odd = final[las]
		else:
			odd = final[las] - final[fir - 1]
		even = las - fir + 1 - odd
		ans = even * (even - 1) * (even - 2) / 6 + odd * (odd - 1) / 2 * even
		print(int(ans))
	t -= 1


def fact(n, m):
	if n == m:
		return 1
	return n * fact(n - 1, m)
T = int(input())
while T > 0:
	(n, q) = input().split()
	n = int(n)
	q = int(q)
	arr = input().split()
	final = [x for x in range(len(arr))]
	j = 0
	for i in arr:
		i = int(i)
		if j == 0:
			final[j] = i % 2
		else:
			final[j] = final[j - 1] + i % 2
		j += 1
	for i in range(q):
		(l, r) = input().split()
		l = int(l) - 1
		r = int(r) - 1
		if l == 0:
			odd = final[r]
		else:
			odd = final[r] - final[l - 1]
		even = r - l + 1 - odd
		ans1 = ans2 = ans = 0
		if even > 2:
			ans1 = fact(even, even - 3) / 6
		if even > 0 and odd > 1:
			ans2 = fact(odd, odd - 2) / 2 * even
		ans = ans1 + ans2
		print(int(ans))
	T -= 1


T = int(input())
for i in range(T):
	(n, Q) = [int(i) for i in input().split()]
	arr = [int(i) for i in input().split()]
	arrE = []
	count = 0
	arrE.append(count)
	for i in range(len(arr)):
		if arr[i] % 2 == 0:
			count = count + 1
			arrE.append(count)
		else:
			arrE.append(count)
	for i in range(Q):
		(L, R) = [int(i) for i in input().split()]
		e = arrE[R] - arrE[L - 1]
		o = R - L + 1 - e
		eC = e * (e - 1) * (e - 2) // 6
		oC = o * (o - 1) // 2 * e
		print(eC + oC)


d = int(input())
for p in range(0, d):
	(n, q) = list(map(int, input().split()))
	a = list(map(int, input().split()))
	c = 0
	d = 0
	x = [0]
	y = [0]
	for j in range(n):
		if a[j] % 2 == 0:
			c = c + 1
		else:
			d = d + 1
		y.append(d)
		x.append(c)
	for i in range(q):
		(l, r) = list(map(int, input().split()))
		if r - l + 1 <= 2:
			print(0)
		else:
			k = x[r] - x[l - 1]
			h = y[r] - y[l - 1]
			print(k * (h * (h - 1)) // 2 + k * (k - 1) * (k - 2) // 6)


import sys
input = sys.stdin.readline

def print(x, end='\n'):
	sys.stdout.write(str(x) + end)
t = int(input())
for i in range(t):
	(n, q) = tuple(map(int, input().split()))
	array = list(map(int, input().split()))
	if array[0] % 2 == 0:
		array[0] = 1
	else:
		array[0] = 0
	for w in range(1, n):
		if array[w] % 2 == 0:
			array[w] = array[w - 1] + 1
		else:
			array[w] = array[w - 1]
	for j in range(q):
		(l, r) = tuple(map(int, input().split()))
		if l == 1:
			even = array[r - 1]
		else:
			even = array[r - 1] - array[l - 2]
		odd = r - l + 1 - even
		count = 0
		count += even * (even - 1) * (even - 2) // 6
		count += odd * (odd - 1) * even // 2
		print(count)


t = int(input())
for i in range(t):
	(n, q) = tuple(map(int, input().split()))
	array = list(map(int, input().split()))
	if array[0] % 2 == 0:
		array[0] = 1
	else:
		array[0] = 0
	for w in range(1, n):
		if array[w] % 2 == 0:
			array[w] = array[w - 1] + 1
		else:
			array[w] = array[w - 1]
	for j in range(q):
		(l, r) = tuple(map(int, input().split()))
		if l == 1:
			even = array[r - 1]
		else:
			even = array[r - 1] - array[l - 2]
		odd = r - l + 1 - even
		count = 0
		count += even * (even - 1) * (even - 2) // 6
		count += odd * (odd - 1) * even // 2
		print(count)


t = int(input())
for _ in range(t):
	(n, q) = map(int, input().split())
	a = list(map(int, input().split()))
	arr = [0] * (n + 1)
	for i in range(1, n + 1):
		if a[i - 1] % 2 == 0:
			arr[i] = arr[i - 1] + 1
		else:
			arr[i] = arr[i - 1]
	for i in range(q):
		(l, r) = map(int, input().split())
		even = arr[r] - arr[l - 1]
		odd = r - l + 1 - even
		even_comb = even * (even - 1) * (even - 2) / 6
		odd_comb = odd * (odd - 1) / 2 * even
		print(int(even_comb + odd_comb))


def evenTuples():
	for _ in range(int(input())):
		(N, Q) = [int(x) for x in input().split()]
		A = [int(x) for x in input().split()]
		(odds, evens) = ([0], [0])
		for a in A:
			if a % 2 is 0:
				evens.append(evens[-1] + 1)
				odds.append(odds[-1])
			else:
				odds.append(odds[-1] + 1)
				evens.append(evens[-1])
		LR = [[int(x) for x in input().split()] for i in range(Q)]
		for (L, R) in LR:
			odd = odds[R] - odds[L - 1]
			even = evens[R] - evens[L - 1]
			ans = even * odd * (odd - 1) // 2 + even * (even - 1) * (even - 2) // 6
			print(ans)
evenTuples()


import operator as op
from functools import reduce

def binomialCoef(n, k):
	C = [[0 for x in range(k + 1)] for x in range(n + 1)]
	for i in range(n + 1):
		for j in range(min(i, k) + 1):
			if j == 0 or j == i:
				C[i][j] = 1
			else:
				C[i][j] = C[i - 1][j - 1] + C[i - 1][j]
	return C[n][k]

def comb(n, r):
	r = min(r, n - r)
	if r < 0:
		return 0
	numer = reduce(op.mul, range(n, n - r, -1), 1)
	denom = reduce(op.mul, range(1, r + 1), 1)
	return numer // denom
for t in range(int(input())):
	(N, Q) = map(int, input().split())
	arr = list(map(int, input().split()))
	(od, ev) = ([0], [0])
	for i in range(N):
		if arr[i] % 2:
			od.append(od[-1] + 1)
			ev.append(ev[-1])
		else:
			ev.append(ev[-1] + 1)
			od.append(od[-1])
	for q in range(Q):
		(l, r) = map(int, input().split())
		od_n = od[r] - od[l - 1]
		ev_n = ev[r] - ev[l - 1]
		ans = comb(od_n, 2) * ev_n + comb(ev_n, 3)
		print(ans)


dp = [[0 for j in range(4)] for i in range(50001)]
for i in range(50001):
	for j in range(4):
		if i == j or j == 0:
			dp[i][j] = 1
		else:
			dp[i][j] = dp[i - 1][j - 1] + dp[i - 1][j]
for _ in range(int(input())):
	(n, q) = map(int, input().split())
	a = [int(i) for i in input().split()]
	even = [0] * (n + 1)
	for i in range(1, n + 1):
		if a[i - 1] & 1:
			even[i] = even[i - 1]
		else:
			even[i] = even[i - 1] + 1
	for i in range(q):
		(l, r) = map(int, input().split())
		ecnt = even[r] - even[l - 1]
		ocnt = r - l + 1 - ecnt
		print(dp[ecnt][3] + dp[ecnt][1] * dp[ocnt][2])


import sys, os.path
from math import gcd, floor, ceil
mod = 1000000007
if os.path.exists('input.txt'):
	sys.stdin = open('input.txt', 'r')
	sys.stdout = open('output.txt', 'w')
input = lambda : sys.stdin.readline().replace('\n', '').strip()
tup = lambda typ=int: map(typ, input().split())
lis = lambda typ=int: list(map(typ, input().split()))
pr = lambda n: sys.stdout.write(str(n) + '\n')
prl = lambda n: sys.stdout.write(str(n) + ' ')

def com(n, x):
	p = 1
	q = 1
	if x > n // 2:
		x = n - x
	for i in range(1, x + 1):
		p *= n
		q *= i
		n -= 1
	return p // q
for _ in range(int(input())):
	(n, q) = map(int, input().split())
	l = list(map(int, input().split()))
	a = []
	(e, o) = (0, 0)
	for i in l:
		if i & 1:
			o += 1
		else:
			e += 1
		a.append((e, o))
	for i in range(q):
		(le, r) = map(int, input().split())
		ans = 0
		if le == 1:
			(e, o) = (a[r - 1][0], a[r - 1][1])
		else:
			(e, o) = (a[r - 1][0] - a[le - 2][0], a[r - 1][1] - a[le - 2][1])
		if o >= 2 and e >= 1:
			ans += com(o, 2) * com(e, 1)
		if e >= 3:
			ans += com(e, 3)
		pr(ans)


t = int(input().strip())
while t:
	(N, Q) = map(int, input().strip().split())
	arr = list(map(int, input().strip().split()))
	prefix_even = [0] * (N + 1)
	for i in range(N):
		if arr[i] % 2 == 0:
			prefix_even[i + 1] = prefix_even[i] + 1
		else:
			prefix_even[i + 1] = prefix_even[i]
	for i in range(Q):
		(l, r) = map(int, input().strip().split())
		even = prefix_even[r] - prefix_even[l - 1]
		odd = r - l + 1 - even
		ans = even * (even - 1) * (even - 2) // 6 + odd * even * (odd - 1) // 2
		print(ans)
	t -= 1


def map_int_input():
	return map(int, input().split())

def list_int_input():
	return [int(x) for x in input().split()]

def solve():
	(n, q) = map_int_input()
	arr = list_int_input()
	even_num_count = [0] * (n + 1)
	for i in range(1, n + 1):
		even_num_count[i] = even_num_count[i - 1] + (1 if arr[i - 1] % 2 == 0 else 0)
	for _ in range(q):
		(l, r) = map_int_input()
		lr_even_count = even_num_count[r] - even_num_count[l - 1]
		lr_odd_count = r - l + 1 - lr_even_count
		first_case = lr_even_count * (lr_even_count - 1) * (lr_even_count - 2) / 6
		second_case = lr_odd_count * (lr_odd_count - 1) / 2 * lr_even_count
		print(int(first_case + second_case))
for _ in range(int(input())):
	solve()


for i in range(int(input())):
	(n, q) = map(int, input().split())
	a = [int(x) for x in input().split()]
	b = [0] * (n + 1)
	for j in range(n):
		if a[j] % 2 == 0:
			b[j + 1] = b[j]
		else:
			b[j + 1] = b[j] + 1
	for j in range(q):
		(l, r) = map(int, input().split())
		so = b[r] - b[l - 1]
		se = r - l + 1 - so
		s = se * (se - 1) * (se - 2) / 6 + se * so * (so - 1) / 2
		print(int(s))


for i in range(int(input())):
	(n, q) = map(int, input().split())
	dp = [0] * (n + 1)
	arr = list(map(int, input().split()))
	for i in range(len(arr)):
		if arr[i] % 2 == 0:
			dp[i + 1] = 1 + dp[i]
		else:
			dp[i + 1] = dp[i]
	for j in range(q):
		(q1, q2) = list(map(int, input().split()))
		ev = dp[q2] - dp[q1 - 1]
		od = q2 - q1 + 1 - ev
		ev_com = ev * (ev - 1) * (ev - 2) // 6
		od_com = od * (od - 1) // 2 * ev
		print(ev_com + od_com)


for _ in range(int(input())):
	(n, q) = map(int, input().split())
	arr = list(map(int, input().split()))
	c1 = 0
	temp = []
	even = []
	for i in arr:
		if i % 2 == 0:
			temp.append(1)
		else:
			temp.append(0)
	even.append(0)
	for i in temp:
		if i == 1:
			c1 += 1
		even.append(c1)
	for _ in range(q):
		(l, r) = map(int, input().split())
		noofevens = even[r] - even[l - 1]
		noofodds = r - l + 1 - noofevens
		print(noofevens * (noofevens - 1) * (noofevens - 2) // 6 + noofodds * (noofodds - 1) // 2 * noofevens)


for t in range(int(input())):
	(n, q) = map(int, input().split())
	odd = [0] * (n + 1)
	even = [0] * (n + 1)
	a = list(map(int, input().strip().split()))
	if a[0] % 2 == 0:
		even[1] = 1
	else:
		odd[1] = 1
	for i in range(1, n):
		if a[i] % 2 == 0:
			even[i + 1] += 1
		else:
			odd[i + 1] += 1
		even[i + 1] += even[i]
		odd[i + 1] += odd[i]
	for _ in range(q):
		(l, r) = map(int, input().split())
		odds = odd[r] - odd[l - 1]
		evens = even[r] - even[l - 1]
		ans = 0
		if odds >= 2:
			ans += odds * (odds - 1) // 2 * evens
		if evens > 2:
			ans += evens * (evens - 1) * (evens - 2) // 6
		print(ans)


for _ in range(int(input())):
	(n, q) = map(int, input().split())
	arr = list(map(int, input().split()))
	prefix = [0] * (n + 1)
	c = 0
	for i in range(n):
		if arr[i] & 1:
			pass
		else:
			c += 1
		prefix[i + 1] = c
	for i in range(q):
		(l, r) = map(int, input().split())
		e = prefix[r] - prefix[l - 1]
		m = r - l + 1
		o = m - e
		ans = 0
		if e >= 3:
			ans += e * (e - 1) * (e - 2) // 6
		if o >= 2 and e > 0:
			ans += e * (o * (o - 1) // 2)
		print(ans)


for _ in range(int(input())):
	(a, b) = map(int, input().split())
	l = list(map(int, input().split()))
	mid = {0: [0, 0]}
	(count1, count2) = (0, 0)
	for i in range(a):
		if l[i] % 2 == 0:
			count1 += 1
		else:
			count2 += 1
		mid[i + 1] = [count1, count2]
	for i in range(b):
		(x, y) = map(int, input().split())
		evens = mid[y][0] - mid[x - 1][0]
		odds = mid[y][1] - mid[x - 1][1]
		print(evens * (evens - 1) * (evens - 2) // 6 + odds * (odds - 1) * evens // 2)


def combination(n, r):
	numerator = 1
	for i in range(n - r + 1, n + 1):
		numerator *= i
	denominator = 1
	for j in range(2, r + 1):
		denominator *= j
	return numerator // denominator
try:
	t = int(input())
	i = 0
	while i < t:
		arr = list(input().split(' '))
		N = int(arr[0])
		Q = int(arr[1])
		A = list(input().split(' '))
		for ind in range(0, len(A)):
			A[ind] = int(A[ind])
		even = [0]
		for ind in range(0, N):
			if A[ind] % 2 == 0:
				even.append(even[ind] + 1)
			else:
				even.append(even[ind])
		j = 0
		while j < Q:
			query = list(input().split(' '))
			L = int(query[0])
			R = int(query[1])
			even_count = even[R] - even[L - 1]
			odd_count = R - L + 1 - even_count
			tuples_count = combination(even_count, 3) + combination(odd_count, 2) * even_count
			print(tuples_count)
			Q -= 1
		t -= 1
except IOError:
	print('IO Exception')


import operator as op
from functools import reduce

def ncr(n, r):
	if n < r:
		return 0
	r = min(r, n - r)
	numer = reduce(op.mul, range(n, n - r, -1), 1)
	denom = reduce(op.mul, range(1, r + 1), 1)
	return numer // denom
T = int(input())
for test in range(T):
	(N, Q) = map(int, input().split())
	nums = list(map(int, input().split()))
	preEven = [0] * len(nums)
	countEven = 0
	for i in range(len(nums)):
		if nums[i] % 2 == 0:
			countEven += 1
			preEven[i] = countEven
		else:
			preEven[i] = countEven
	for query in range(Q):
		(l, r) = map(int, input().split())
		even = 0
		odd = 0
		if l <= 1:
			even = preEven[r - 1]
		else:
			even = preEven[r - 1] - preEven[l - 2]
		odd = r - l + 1 - even
		totalComb = ncr(even, 3) + ncr(odd, 2) * even
		print(totalComb)


T = int(input())
while T:
	(n, q) = map(int, input().split(' '))
	n_list = [0] * (n + 1)
	i_l = list(map(int, input().split(' ')))
	n_list[1:n + 1] = i_l
	for i in range(1, len(n_list)):
		if n_list[i] % 2 == 0:
			n_list[i] = n_list[i - 1] + 1
		else:
			n_list[i] = n_list[i - 1]
	while q:
		(l, r) = map(int, input().split(' '))
		even = n_list[r] - n_list[l - 1]
		odd = r - l + 1 - even
		ec3 = even * (even - 1) * (even - 2) // 6
		oc2 = odd * (odd - 1) // 2
		res = ec3 + oc2 * even
		print(res)
		q = q - 1
	T = T - 1


def NC3(x):
	if x < 3:
		return 0
	elif x == 3:
		return 1
	else:
		return x * (x - 1) * (x - 2) // 6

def NC2(x):
	if x < 2:
		return 0
	elif x == 2:
		return 1
	else:
		return x * (x - 1) // 2
t = int(input())
for _ in range(t):
	(n, q) = [int(x) for x in input().split()]
	nums = [int(x) for x in input().split()]
	even_dp = [0] * len(nums)
	for (i, n) in enumerate(nums):
		if i == 0:
			even_dp[i] = 0 + (n % 2 == 0)
		else:
			even_dp[i] = even_dp[i - 1] + (n % 2 == 0)
	for _ in range(q):
		(l, r) = [int(x) - 1 for x in input().split()]
		even = even_dp[r] - (0 if not l else even_dp[l - 1])
		odd = r - l + 1 - even
		res = NC3(even) + NC2(odd) * even
		print(res)


m = int(input())
for i in range(m):
	(n, q) = [int(x) for x in input().split()]
	a = [0] * (n + 1)
	x = [int(o) for o in input().split()]
	for k in range(n):
		if x[k] % 2 == 0:
			a[k + 1] = a[k] + 1
		else:
			a[k + 1] = a[k]
	for j in range(q):
		(l, r) = [int(x) for x in input().split()]
		even = a[r] - a[l - 1]
		odd = r - l + 1 - even
		ans = even * (even - 1) * (even - 2) // 6 + odd * (odd - 1) // 2 * even
		print(ans)


T = int(input())
for i in range(T):
	(N, Q) = map(int, input().split())
	A = list(map(int, input().strip().split()))[:N]
	E = [0] * (N + 1)
	for k in range(N):
		if A[k] % 2 == 0:
			E[k + 1] = 1 + E[k]
		else:
			E[k + 1] = E[k]
	for j in range(Q):
		(L, R) = map(int, input().split())
		a = E[R] - E[L - 1]
		b = R - L + 1 - a
		ans = int(a * (a - 1) * (a - 2) / 6 + a * b * (b - 1) / 2)
		print(ans)


for _ in range(int(input())):
	(n, q) = map(int, input().split())
	arr = list(map(int, input().split()))
	res = []
	ans = []
	count = 0
	for i in range(n):
		if arr[i] % 2 == 0:
			count += 1
		res.append(count)
		ans.append(i + 1 - count)
	for _ in range(q):
		(l, r) = map(int, input().split())
		if l > 1:
			e = res[r - 1] - res[l - 1] + (res[l - 1] - res[l - 2])
			o = ans[r - 1] - ans[l - 1] + (ans[l - 1] - ans[l - 2])
		else:
			e = res[r - 1]
			o = ans[r - 1]
		c = e * (e - 1) * (e - 2) // 6 + e * (o * (o - 1) // 2)
		print(c)


for _ in range(int(input())):
	(n, q) = map(int, input().split())
	l = list(map(int, input().split()))
	even = [0]
	odd = [0]
	for i in l:
		if i % 2 == 0:
			even.append(even[-1] + 1)
			odd.append(odd[-1])
		else:
			even.append(even[-1])
			odd.append(odd[-1] + 1)
	for i in range(q):
		(v, k) = map(int, input().split())
		e = even[k] - even[v - 1]
		o = odd[k] - odd[v - 1]
		a = o * (o - 1) * e // 2
		b = e * (e - 1) * (e - 2) // 6
		print(a + b)


t = int(input())
for i in range(t):
	(n, q) = [int(x) for x in input().split()]
	A = [int(x) for x in input().split()]
	p = [0]
	for i in A:
		if i % 2 != 0:
			p.append(p[-1] + 1)
		else:
			p.append(p[-1])
	for i in range(q):
		(l, r) = [int(x) for x in input().split()]
		o = p[r] - p[l - 1]
		e = r - l + 1 - o
		if r - l + 1 < 2:
			print(0)
		else:
			print(o * (o - 1) // 2 * e + e * (e - 1) * (e - 2) // 6)


for _ in range(int(input())):
	(n, q) = map(int, input().split())
	l1 = list(map(int, input().split()))
	l2 = [0] * (n + 1)
	for i in range(n):
		if l1[i] % 2 == 0:
			l2[i + 1] = l2[i] + 1
		else:
			l2[i + 1] = l2[i]
	for i in range(q):
		(l, r) = map(int, input().split())
		even = l2[r] - l2[l - 1]
		odd = r - l + 1 - even
		c1 = even * (even - 1) * (even - 2) // 6
		c2 = odd * (odd - 1) // 2 * even
		print(c1 + c2)


t = int(input())
while t > 0:
	(n, q) = map(int, input().split())
	arr = list(map(int, input().strip().split()))
	even = [0] * n
	odd = [0] * n
	countOdd = 0
	countEven = 0
	for i in range(n):
		if arr[i] % 2 == 0:
			countEven += 1
		else:
			countOdd += 1
		even[i] = countEven
		odd[i] = countOdd
	for i in range(q):
		(l, r) = map(int, input().split())
		e = even[r - 1] - even[l - 1]
		o = odd[r - 1] - odd[l - 1]
		if arr[l - 1] % 2 == 0:
			e += 1
		else:
			o += 1
		a = 0
		b = 0
		if e >= 3:
			a = e * (e - 1) * (e - 2) // 6
		if e >= 1 and o >= 2:
			b = e * (o * (o - 1) // 2)
		ans = a + b
		print(ans)
	t = t - 1


from math import *

def printNcR(n, r):
	if n < r:
		return 0
	p = 1
	k = 1
	if n - r < r:
		r = n - r
	if r != 0:
		while r:
			p *= n
			k *= r
			m = gcd(p, k)
			p //= m
			k //= m
			n -= 1
			r -= 1
	else:
		p = 1
	return p
for _ in range(int(input())):
	(n, k) = map(int, input().split())
	l = list(map(int, input().split()))
	s = [[0, 0] for _ in range(n + 1)]
	for i in range(n):
		if l[i] % 2 == 0:
			s[i + 1][0] = s[i][0] + 1
			s[i + 1][1] = s[i][1]
		else:
			s[i + 1][1] = s[i][1] + 1
			s[i + 1][0] = s[i][0]
	for i in range(k):
		(a, b) = map(int, input().split())
		odd = s[b][1] - s[a - 1][1]
		even = s[b][0] - s[a - 1][0]
		print(printNcR(even, 3) + even * printNcR(odd, 2))


import numpy as np

def comb(n, r):
	r = min(r, n - r)
	if r < 0:
		return 0
	import operator as op
	from functools import reduce
	numer = reduce(op.mul, range(n, n - r, -1), 1)
	denom = reduce(op.mul, range(1, r + 1), 1)
	return numer // denom
t = int(input())
odd_map = np.zeros(1000000 + 1, dtype=int)
even_map = np.zeros(1000000 + 1, dtype=int)
while t > 0:
	(n, q) = list(map(int, input().split()))
	a = list(map(int, input().split()))
	for i in range(len(a)):
		odd_map[i + 1] = 1 if a[i] % 2 == 1 else 0
		even_map[i + 1] = 1 if a[i] % 2 == 0 else 0
	odd_map = np.add.accumulate(odd_map)
	even_map = np.add.accumulate(even_map)
	while q > 0:
		(start, end) = list(map(int, input().split()))
		n_odd = odd_map[end] - odd_map[start - 1]
		n_even = even_map[end] - even_map[start - 1]
		result = comb(n_odd, 2) * comb(n_even, 1) + comb(n_even, 3)
		print(result)
		q -= 1
	t -= 1


t = int(input())
for i in range(t):
	ls1 = input().split(' ')
	N = int(ls1[0])
	Q = int(ls1[1])
	ls2 = [int(x) for x in input().split(' ')]
	evenlis = []
	evenc = 0
	oddlis = []
	oddc = 0
	for j in range(N):
		if ls2[j] % 2 == 0:
			evenc += 1
			evenlis.append(evenc)
			oddlis.append(oddc)
		else:
			oddc += 1
			evenlis.append(evenc)
			oddlis.append(oddc)
	for ii in range(Q):
		lls = input().split(' ')
		L = int(lls[0])
		R = int(lls[1])
		if L == 1:
			even_nos = evenlis[R - 1]
			odd_nos = oddlis[R - 1]
		else:
			even_nos = evenlis[R - 1] - evenlis[L - 2]
			odd_nos = oddlis[R - 1] - oddlis[L - 2]
		print(even_nos * (even_nos - 1) * (even_nos - 2) // 6 + odd_nos * (odd_nos - 1) // 2 * even_nos)


for _ in range(int(input())):
	(n, q) = map(int, input().split())
	l = list(map(int, input().split()))
	m = [0]
	c = 0
	for i in range(len(l)):
		if l[i] % 2 == 0:
			c = c + 1
			m.append(c)
		else:
			m.append(c)
	for i in range(q):
		(a, b) = map(int, input().split())
		e = m[b] - m[a - 1]
		odd = b - e - a + 1
		ans1 = e * (e - 1) * (e - 2) / 6
		ans2 = odd * (odd - 1) * e / 2
		ans = ans1 + ans2
		print(int(ans))


for testcase in range(int(input())):
	(n, k) = map(int, input().split())
	l = list(map(int, input().split()))
	even = 0
	final = []
	for x in l:
		if x % 2 == 0:
			even += 1
		final.append(even)
	for q in range(k):
		(l, r) = map(int, input().split())
		if l != 1:
			total_even = final[r - 1] - final[l - 2]
		else:
			total_even = final[r - 1]
		total_odd = r - l - total_even + 1
		print(total_even * (total_even - 1) * (total_even - 2) // 6 + total_odd * (total_odd - 1) // 2 * total_even)


for t in range(int(input())):
	inp = input().split()
	n = int(inp[0])
	q = int(inp[1])
	arr = input().split()
	eve = [0]
	for i in range(len(arr)):
		if int(arr[i]) % 2 == 0:
			eve.append(eve[-1] + 1)
		else:
			eve.append(eve[-1])
	for i in range(q):
		lr = input().split()
		l = int(lr[0])
		r = int(lr[1])
		e = eve[r] - eve[l - 1]
		o = r - l + 1 - e
		count = int(e * o * (o - 1) / 2 + e * (e - 1) * (e - 2) / 6)
		print(count)


for _ in range(int(input())):
	(n, q) = map(int, input().split())
	lst = list(map(int, input().split()))
	arr = [0]
	for i in range(n):
		if lst[i] & 1:
			arr.append(arr[i] + 1)
		else:
			arr.append(arr[i])
	for i in range(q):
		(l, r) = map(int, input().split())
		odd = arr[r] - arr[l - 1]
		even = r - l + 1 - odd
		res = even * (even - 1) * (even - 2) / 6 + even * odd * (odd - 1) / 2
		print(int(res))


from math import factorial
for i in range(int(input())):
	(length, q) = [int(x) for x in input().split()]
	nums = [int(x) for x in input().split()]
	odd = 0
	even = 0
	pref_odd = [0] * (len(nums) + 1)
	pref_even = [0] * (len(nums) + 1)
	for k in range(len(nums)):
		if nums[k] % 2 != 0:
			odd += 1
		else:
			even += 1
		pref_even[k + 1] = even
		pref_odd[k + 1] = odd
	for j in range(q):
		(l, r) = [int(x) for x in input().split()]
		odd = pref_odd[r] - pref_odd[l - 1]
		even = pref_even[r] - pref_even[l - 1]
		even_count = even * (even - 1) * (even - 2) // 6
		ans = odd * (odd - 1) // 2 * even + even_count
		print(ans)


import math

def combination(n, r):
	return math.comb(n, r)

def listing():
	return list(map(int, input().split()))

def intp():
	return int(input())

def inp():
	return input()

def inpspl():
	return input().split()

def mapping():
	return map(int, input().split())

def sqrt(n):
	return math.sqrt(n)

def gcd(a, b):
	return math.gcd(a, b)

def lcm(a, b):
	return a * b // gcd(a, b)

def p(s):
	print(f'{s}')

def lsetl(lst):
	return list(set(lst))

def nCr(n, r):
	f = math.factorial
	return f(n) // f(r) // f(abs(n - r))

def solve():
	for _ in range(intp()):
		(n, q) = mapping()
		nlst = listing()
		count = 0
		ls = [0] * (n + 1)
		for i in range(n):
			if nlst[i] % 2 == 0:
				count += 1
			ls[i + 1] = count
		for __ in range(q):
			(l, r) = mapping()
			even = ls[r] - ls[l - 1]
			odd = r - l + 1 - even
			aa = even * (even - 1) * (even - 2) // 6
			bb = odd * (odd - 1) // 2
			print(aa + bb * even)
solve()


import sys
import os.path
import math
import copy
from sys import stdin, stdout
from collections import *
from math import gcd, ceil, floor
mod = int(1000000000.0 + 7)
m1 = float('inf')
if os.path.exists('Updated prg/Input3d.txt'):
	sys.stdout = open('Updated prg/Output3d.txt', 'w')
	sys.stdin = open('Updated prg/Input3d.txt', 'r')

def sinp():
	return input()

def ninp():
	return int(sinp())

def mapinp():
	return map(int, sinp().split())

def smapinp():
	return map(str, sinp().split())

def linp():
	return list(mapinp())

def sl():
	return list(sinp().split())

def power(n):
	return 1 << n

def prnt(a):
	print(a)

def prntl(a):
	print(a, end=' ')

def prntlist(l1):
	print(*l1)
for _ in range(ninp()):
	(N, Q) = mapinp()
	A = linp()
	A_new = [0] * (N + 1)
	for i in range(1, N + 1):
		A_new[i] = A[i - 1]
	prefix = [0] * (N + 1)
	for i in range(1, N + 1):
		if A_new[i] % 2 == 0:
			prefix[i] = prefix[i - 1] + 1
		else:
			prefix[i] = prefix[i - 1]
	for _ in range(Q):
		count = 0
		(L, R) = mapinp()
		even = prefix[R] - prefix[L - 1]
		odd = R - L + 1 - even
		count = even * (even - 1) * (even - 2) // 6
		count = count + odd * (odd - 1) // 2 * even
		prnt(count)


def fun(a):
	ans = [0] * (len(a) + 1)
	u = 1
	for i in a:
		if i % 2 == 0:
			ans[u] = ans[u - 1] + 1
		else:
			ans[u] = ans[u - 1]
		u += 1
	return ans
for _ in range(int(input())):
	(n, q) = map(int, input().split())
	li = [int(x) for x in input().split()]
	ans_arr = fun(li)
	for i in range(q):
		(l, r) = map(int, input().split())
		even = ans_arr[r] - ans_arr[l - 1]
		odd = r - l + 1 - even
		even_combo = even * (even - 1) * (even - 2) // 6
		odd_combo = odd * (odd - 1) // 2 * even
		print(even_combo + odd_combo)


import sys, math, io, os, time, itertools, collections
mod = 10 ** 9 + 7
sys.setrecursionlimit(10000)
i = sys.stdin.readline
global start, end

def isin(l, x):
	left = 0
	right = len(l) - 1
	if x < l[0]:
		return -1
	while left <= right:
		mid = left + (right - left) // 2
		if l[mid] == x:
			return mid
		elif l[mid] < x:
			ans = mid
			left = mid + 1
		else:
			right = mid - 1
	return ans

def ispal(l):
	n = len(l)
	for i in range(n // 2 + 1):
		if l[i] != l[n - i - 1]:
			return False
	return True

def ccarray(l):
	d = {l[k]: k for k in range(len(l))}
	m = sorted(d)
	return [d[m[k]] for k in range(len(l))]

def is_prime(n):
	if n <= 3:
		return n > 1
	if n % 2 == 0 or n % 3 == 0:
		return False
	k = 5
	while k ** 2 <= n:
		if n % k == 0 or n % (k + 2) == 0:
			return False
		k += 6
	return True

def sieve(n):
	prime = [True for k in range(n + 1)]
	p = 2
	while p * p <= n:
		if prime[p] == True:
			for k in range(p * p, n + 1, p):
				prime[k] = False
		p += 1

def main():
	(n, q) = [int(k) for k in i().split()]
	a = [int(k) % 2 for k in i().split()]
	z_count = [0 for _ in range(n + 1)]
	o_count = [0 for _ in range(n + 1)]
	if a[0] == 1:
		o_count[1] = 1
	else:
		z_count[1] = 1
	for k in range(2, n + 1):
		if a[k - 1] == 0:
			z_count[k] = z_count[k - 1] + 1
			o_count[k] = o_count[k - 1]
		else:
			o_count[k] = o_count[k - 1] + 1
			z_count[k] = z_count[k - 1]
	for _ in range(q):
		(l, r) = [int(k) for k in i().split()]
		z = z_count[r] - z_count[l - 1]
		o = o_count[r] - o_count[l - 1]
		ans = z * (z - 1) * (z - 2) // 6 + z * o * (o - 1) // 2
		sys.stdout.write(str(ans) + '\n')
t = 1
t = int(i())
start = time.perf_counter()
for _ in range(t):
	main()
end = time.perf_counter()