A number M is said to be a *Mystical Number* with respect to a number X if (M \oplus X) > (M \& X).

You are given an array A of size N. You are also given Q queries. Each query consists of three integers L, R, and X.

For each query, find the count of *Mystical Numbers* in the subarray A[L:R] with respect to the number X. 

Notes:
\oplus represents the [Bitwise XOR] operation and \& represents the [Bitwise AND] operation.
A[L:R] denotes the subarray A[L], A[L+1], \ldots, A[R].

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

- The first line contains a single integer T - the number of test cases. Then the test cases follow.
- The first line of each test case contains an integer N - the size of the array A.
- The second line of each test case contains N space-separated integers A_{1}, A_{2}, \dots, A_{N} denoting the array A.
- The third line of each test case contains an integer Q - denoting the number of queries.
- The i^{th} of the next Q lines contains three space-separated integers L , R and X.

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

For each testcase, 
- For each query, print in a new line, the count of *Mystical Numbers* among A[L], A[L+1], \ldots, A[R] with respect to the number X. 

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

$1 ≤ T ≤ 100$
$1 ≤ N ≤ 2 \cdot 10^{5}$
$0 ≤ A_{i} < 2^{31}$
$1 ≤ Q ≤ 2 \cdot 10^{5}$
$1 ≤ L ≤ R ≤ N$
$0 ≤ X < 2^{31}$
- Sum of $N$ over all test cases does not exceed $2 \cdot 10^{5}$.
- Sum of $Q$ over all test cases does not exceed $2 \cdot 10^{5}$.

----- Sample Input 1 ------ 
1
5
1 2 3 4 5
2
1 5 4
2 5 2
----- Sample Output 1 ------ 
3
2
----- explanation 1 ------ 
Test case $1$:  
- Query $1$: $L = 1 , R = 5 , X = 4$. 
- $A_{1} \oplus X = 5, A_{1} \& X = 0$.
- $A_{2} \oplus X = 6, A_{2} \& X = 0$.
- $A_{3} \oplus X = 7, A_{3} \& X = 0$.
- $A_{4} \oplus X = 0, A_{4} \& X = 4$.
- $A_{5} \oplus X = 1, A_{5} \& X = 4$.

Mystical numbers are $A_{1} , A_{2},$ and $A_{3}$ with respect to $4$. Therefore, the answer to this query is $3$.
- Query $2$: $L = 2 , R = 5 , X = 2$.
- $A_{2} \oplus X = 0, A_{2} \& X = 2$.
- $A_{3} \oplus X = 1, A_{3} \& X = 2$.
- $A_{4} \oplus X = 6, A_{4} \& X = 0$.
- $A_{5} \oplus X = 7, A_{5} \& X = 0$.

Mystical numbers are $A_{4}$ and $A_{5}$ with respect to $2$. Therefore , the answer to this query is $2$.

Source: codechef | Difficulty: MEDIUM_HARD
Tags: Range queries

Bit manipulation

Mathematics


Solutions:
import math
t = int(input())
for _ in range(t):
	n = int(input())
	a = list(map(int, input().split()))
	cd = {}
	for i in range(32):
		cd[i] = 0
	counts = [cd]
	for j in range(n):
		newc = counts[j].copy()
		if a[j] != 0:
			digs = int(math.log2(a[j])) + 1
		if a[j] == 0:
			digs = 0
		newc[digs] += 1
		counts.append(newc)
	q = int(input())
	for _ in range(q):
		(l, r, x) = map(int, input().split())
		if x != 0:
			xd = int(math.log2(x)) + 1
		if x == 0:
			xd = 0
		print(r - l + 1 - (counts[r][xd] - counts[l - 1][xd]))


import math as m

def msb(k):
	cnt = 0
	while k:
		k = k >> 1
		cnt += 1
	return cnt
for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	for i in range(n):
		a[i] = msb(a[i])
	lst = [[None] * n for _ in range(33)]
	for i in range(33):
		c = 0
		for j in range(n):
			if a[j] == i:
				c += 1
				lst[i][j] = c
			else:
				lst[i][j] = c
	q = int(input())
	for l in range(q):
		(l, r, x) = map(int, input().split())
		x = msb(x)
		l = l - 1
		r = r - 1
		if a[l] == x:
			print(r - l - (lst[x][r] - lst[x][l]))
		else:
			print(r - l + 1 - (lst[x][r] - lst[x][l]))


import math as mt
test_case = int(input())
for test in range(test_case):
	n = int(input())
	a = list(map(int, input().split()))
	q = int(input())
	p = {}
	for i in range(32):
		p[i] = 0
	count = [p]
	for j in range(n):
		temp = count[j].copy()
		if a[j] != 0:
			highestBit = int(mt.log2(a[j])) + 1
		else:
			highestBit = 0
		temp[highestBit] += 1
		count.append(temp)
	for _ in range(q):
		(L, R, X) = map(int, input().split())
		if X != 0:
			xd = int(mt.log2(X)) + 1
		else:
			xd = 0
		print(R - L + 1 - (count[R][xd] - count[L - 1][xd]))


import math

def helper(n):
	if n == 0:
		return 0
	bits = 1
	while n >> 1:
		n = n >> 1
		bits += 1
	return bits
for _ in range(int(input())):
	n = int(input())
	arr = list(map(int, input().split()))
	que = int(input())
	res = []
	for i in range(que):
		res.append(list(map(int, input().split())))
	myst = [[0 for p in range(n + 1)] for k in range(33)]
	for k in range(1, n + 1):
		ms = helper(arr[k - 1])
		for j in range(33):
			myst[j][k] = myst[j][k - 1] + (j == ms)
	for a in res:
		s = helper(a[2])
		print(a[1] - a[0] + 1 - myst[s][a[1]] + myst[s][a[0] - 1])


from typing import Iterable
import numpy as np
bit_length = lambda arr: np.ceil(np.log2(arr + 1)).astype(int)

def prepare(n: int, a: Iterable[int]) -> np.ndarray:
	bit_lengths = bit_length(np.fromiter(a, dtype=int))
	prefix_counts = (np.hstack(([-1], bit_lengths)) == np.arange(32).reshape(-1, 1)).cumsum(axis=1)
	return prefix_counts

def query(prefix_counts: np.ndarray, l: int, r: int, x: int) -> int:
	bl = x.bit_length()
	return r - l - (prefix_counts[bl, r] - prefix_counts[bl, l])

def run():
	t = int(input())
	for _ in range(t):
		n = int(input())
		a = map(int, input().split())
		ds = prepare(n, a)
		q = int(input())
		for _ in range(q):
			(l, r, x) = map(int, input().split())
			answer = query(ds, l - 1, r, x)
			print(answer)
run()


import math
for _ in range(int(input())):
	N = int(input())
	mainArray = list(map(int, input().split()))
	Queries = int(input())
	P = {}
	for i in range(32):
		P[i] = 0
	counts = [P]
	for j in range(N):
		tempArray = counts[j].copy()
		if mainArray[j] != 0:
			highestBit = int(math.log2(mainArray[j])) + 1
		else:
			highestBit = 0
		tempArray[highestBit] += 1
		counts.append(tempArray)
	for _ in range(Queries):
		(L, R, X) = map(int, input().split())
		if X != 0:
			xd = int(math.log2(X)) + 1
		else:
			xd = 0
		print(R - L + 1 - (counts[R][xd] - counts[L - 1][xd]))


t = int(input())
for i in range(t):
	n = int(input())
	arr = list(map(int, input().split()))
	sett = [[0 for i in range(32)] for j in range(n + 1)]
	for i in range(n):
		ele = arr[i]
		msb = 0
		while ele > 0:
			msb += 1
			ele = ele // 2
		for k in range(32):
			sett[i + 1][k] = sett[i][k]
		sett[i + 1][msb] += 1
	q = int(input())
	for i in range(q):
		count = 0
		vv = list(map(int, input().split()))
		l = vv[0]
		r = vv[1]
		x = vv[2]
		ms = 0
		while x > 0:
			ms += 1
			x = x // 2
		for m in range(32):
			if m != ms:
				count += sett[r][m] - sett[l - 1][m]
		print(count)


t = int(input())
for i in range(t):
	n = int(input())
	arr = list(map(int, input().split()))
	res = []
	for k in range(32):
		L = []
		c = 0
		for l in range(n):
			if k == 0:
				if arr[l] == 0:
					c += 1
				L.append(c)
			else:
				a = bin(arr[l])[2:]
				if len(a) == k and a != '0':
					c += 1
				L.append(c)
		res.append(L)
	q = int(input())
	for j in range(q):
		(l, r, x) = list(map(int, input().split()))
		if x == 0:
			b = 0
		else:
			b = len(bin(x)[2:])
		if l - 1 == 0:
			tot = res[b][r - 1]
		else:
			tot = res[b][r - 1] - res[b][l - 2]
		print(r - l + 1 - tot)


import math

def msb(s):
	if s == 0:
		return 0
	biti = 1
	while s >> 1:
		s = s >> 1
		biti += 1
	return biti
for i in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	q = int(input())
	b = []
	for i in range(q):
		b.append(list(map(int, input().split())))
	prec = [[0 for p in range(n + 1)] for j in range(33)]
	for k in range(1, n + 1):
		msbi = msb(a[k - 1])
		for j in range(33):
			prec[j][k] = prec[j][k - 1] + (j == msbi)
	for l in b:
		s = msb(l[2])
		print(l[1] - l[0] + 1 - prec[s][l[1]] + prec[s][l[0] - 1])


import math
for _ in range(int(input())):
	n = int(input())
	arr = list(map(int, input().split()))
	memo = [[0] for i in range(32)]
	arrr = [None] + [int(math.log(i, 2)) + 1 if i != 0 else 0 for i in arr]
	for i in range(32):
		for j in range(1, n + 1):
			if i == arrr[j]:
				memo[i].append(memo[i][-1])
			else:
				memo[i].append(memo[i][-1] + 1)
	for _ in range(int(input())):
		(l, r, x) = map(int, input().split())
		x = int(math.log(x, 2)) + 1 if x != 0 else 0
		print(memo[x][r] - memo[x][l - 1])


for i in range(int(input())):
	n = int(input())
	arr = list(map(int, input().split()))
	li = []
	for i in arr:
		if i == 0:
			li.append(0)
		elif i == 1:
			li.append(1)
		else:
			j = 0
			b = i
			while b > 0:
				b = b >> 1
				j += 1
			li.append(j)
	l1 = [[0 for k in range(n)] for j in range(32)]
	b = li[0]
	l1[b][0] = 1
	for j in range(1, n):
		b = li[j]
		l1[b][j] = l1[b][j - 1] + 1
		for k in range(32):
			if k != b:
				l1[k][j] = l1[k][j - 1]
	q = int(input())
	for i in range(q):
		(L, R, X) = map(int, input().split())
		x = 0
		if X == 0:
			x = 0
		elif X == 1:
			x = 1
		else:
			i = 0
			c = X
			while c > 0:
				c = c >> 1
				i += 1
			x = i
		if L > 1:
			print(R - L + 1 - (l1[x][R - 1] - l1[x][L - 2]))
		else:
			print(R - L + 1 - l1[x][R - 1])


T = int(input())
for t in range(T):
	N = int(input())
	A = [int(a) for a in input().split()]
	B = []
	for a in A:
		if a == 0:
			B.append(0)
		elif a == 1:
			B.append(1)
		else:
			i = 0
			b = a
			while b > 0:
				b = b >> 1
				i += 1
			B.append(i)
	C = [[0 for j in range(N)] for i in range(32)]
	b = B[0]
	C[b][0] = 1
	for i in range(1, N):
		b = B[i]
		C[b][i] = C[b][i - 1] + 1
		for j in range(32):
			if j != b:
				C[j][i] = C[j][i - 1]
	Q = int(input())
	for i in range(Q):
		(L, R, X) = map(int, input().split())
		x = 0
		if X == 0:
			x = 0
		elif X == 1:
			x = 1
		else:
			i = 0
			c = X
			while c > 0:
				c = c >> 1
				i += 1
			x = i
		if L > 1:
			print(R - L + 1 - (C[x][R - 1] - C[x][L - 2]))
		else:
			print(R - L + 1 - C[x][R - 1])


from math import log2

def query(bits, L, R, X):
	L = L - 1
	R = R - 1
	s = 0
	if X == 0:
		b = 0
	else:
		b = 1 + int(log2(X))
	for bit in range(32):
		if bit != b:
			s += bits[bit][R] - (bits[bit][L - 1] if L != 0 else 0)
	return s
for test in range(int(input())):
	N = int(input())
	A = list(map(int, input().split()))
	bits = [[0 for i in range(N)] for bit in range(32)]
	for i in range(N):
		if A[i] == 0:
			b = 0
		else:
			b = 1 + int(log2(A[i]))
		for bit in range(32):
			bits[bit][i] = bits[bit][i - 1] + (bit == b) if i != 0 else int(bit == b)
	M = int(input())
	for i in range(M):
		(L, R, X) = map(int, input().split())
		print(query(bits, L, R, X))


ri = lambda : int(input())
rl = lambda : list(map(int, input().split()))
rs = lambda : input()
from collections import defaultdict
import sys
import math
sys.setrecursionlimit(100000000)
t = ri()
for test in range(t):
	n = ri()
	arr = rl()
	dp = [[0 for i in range(32)] for j in range(n + 1)]
	for i in range(n):
		setBit = 0 if arr[i] == 0 else int(math.log(arr[i], 2)) + 1
		for j in range(32):
			if setBit == j:
				dp[i + 1][j] = dp[i][j] + 1
			else:
				dp[i + 1][j] = dp[i][j]
	q = ri()
	for _ in range(q):
		(l, r, x) = rl()
		msb = 0 if x == 0 else int(math.log(x, 2)) + 1
		print(r - l + 1 - (dp[r][msb] - dp[l - 1][msb]))


from math import log
t = int(input())
for _ in range(t):
	n = int(input())
	l = [int(x) for x in input().split()]
	dp = [[0 for i in range(33)] for j in range(n)]
	pre = [0] * n
	for i in range(n):
		if l[i] != 0:
			x = int(log(l[i], 2)) + 1
			dp[i][x] = 1
		else:
			dp[i][0] = 1
	for i in range(1, n):
		for j in range(33):
			dp[i][j] = dp[i][j] + dp[i - 1][j]
	q = int(input())
	for i in range(q):
		(l, r, x) = map(int, input().split())
		(l, r) = (l - 1, r - 1)
		if x != 0:
			setbit = int(log(x, 2)) + 1
		else:
			setbit = 0
		if l == 0:
			print(r - l + 1 - dp[r][setbit])
		else:
			print(r - l + 1 - (dp[r][setbit] - dp[l - 1][setbit]))


def calculateMSB(number):
	if number == 0:
		return 0
	block = 0
	while number >> block:
		block += 1
	return block

def solution():
	N = int(input())
	array = list(map(int, input().split()))
	p = [[0 for i in range(32)] for i in range(N + 1)]
	for i in range(N):
		b = calculateMSB(array[i])
		for j in range(32):
			p[i + 1][j] = p[i][j] + (b == j)
	Q = int(input())
	while Q:
		(L, R, X) = map(int, input().split())
		b = calculateMSB(X)
		ans = R - L + 1 - (p[R][b] - p[L - 1][b])
		print(ans)
		Q -= 1
T = int(input())
while T:
	solution()
	T -= 1


import math
t = int(input())
for i in range(t):
	n = int(input())
	arr = list(map(int, input().split()))
	mx = max(arr)
	lg_mx = math.floor(math.log(mx, 2))
	ans = [0] * (lg_mx + 1)
	dic = {}
	zeros = [0] * n
	zero = 0
	for (ind, i) in enumerate(arr):
		if i == 0:
			zero += 1
			zeros[ind] += zero
			dic[ind] = ans.copy()
			continue
		zeros[ind] = zero
		lg = math.floor(math.log(i, 2))
		ans[lg] += 1
		dic[ind] = ans.copy()
	q = int(input())
	for i in range(q):
		(l, r, x) = list(map(int, input().split()))
		if x == 0:
			if l > 1:
				cnt = zeros[r - 1] - zeros[l - 2]
			else:
				cnt = zeros[r - 1]
			if cnt == r - l + 1:
				print(0)
				continue
			else:
				print(r - l + 1 - cnt)
				continue
		lg = math.floor(math.log(x, 2))
		if lg > lg_mx:
			print(r - l + 1)
			continue
		if l == 1 and r == n:
			print(r - l + 1 - dic[r - 1][lg])
		elif l > 1:
			print(r - l + 1 - dic[r - 1][lg] + dic[l - 2][lg])
		else:
			print(r - l + 1 - dic[r - 1][lg])


for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	q = int(input())
	o = {x: [1 for _ in range(n)] for x in range(1, 33)}
	for (i, item) in enumerate(a):
		e = bin(item)[2:]
		index = None
		for (j, digit) in enumerate(e[::-1]):
			if digit == '1':
				index = j + 1
		if index:
			o[index][i] = 0
	u = {}
	zero_count = [0 for _ in range(n)]
	for (i, item) in enumerate(a):
		if item == 0:
			zero_count[i] = 1
	zero_count_u = []
	for (i, item) in enumerate(zero_count):
		j = item
		if i:
			j += zero_count_u[-1]
		zero_count_u.append(j)
	for (key, value) in o.items():
		g = []
		for (i, item) in enumerate(value):
			h = item
			if i:
				h += g[-1]
			g.append(h)
		u[key] = g
	for _ in range(q):
		(l, r, x) = map(int, input().split())
		e = bin(x)[2:]
		b = len(e)
		l -= 1
		r -= 1
		y = u[b][r]
		if l:
			y -= u[b][l - 1]
		if x == 0:
			ans = r - l + 1
			d = zero_count_u[r]
			if l:
				d -= zero_count_u[l - 1]
			print(ans - d)
			continue
		print(y)


import sys
sys.setrecursionlimit(10 ** 5)

def hsb(x):
	for i in range(31, -1, -1):
		if x & 1 << i:
			return i
	return 32

def pro(arr, q):
	n = len(arr)
	lst = [[0] * 33]
	for i in range(n):
		if i:
			lst.append(lst[i - 1].copy())
		lst[i][hsb(arr[i])] += 1
	for (l, r, x) in q:
		l -= 1
		r -= 1
		R = lst[r][hsb(x)]
		if l > 0:
			L = lst[l - 1][hsb(x)]
		else:
			L = 0
		print(r - l + 1 - (R - L))
t = int(input())
for i in range(t):
	n = int(input())
	arr = list(map(int, input().split()))
	q = []
	qu = int(input())
	for i in range(qu):
		q.append(map(int, input().split()))
	pro(arr, q)


import sys
import math
import bisect
import heapq
from bisect import bisect_right
from sys import stdin, stdout

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

def get_int():
	return int(sys.stdin.readline())

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

def get_list_of_list(n):
	return [list(map(int, sys.stdin.readline().strip().split())) for _ in range(n)]

def get_string():
	return sys.stdin.readline().strip()

def myceil(x, y):
	return (x + y - 1) // y

def Solution():
	pass

def getValue(a, l, r):
	i = 0
	j = len(a) - 1
	lf = -1
	while i >= 0 and j < len(a) and (i <= j):
		md = (i + j) // 2
		if a[md] >= l:
			i = md - 1
			lf = md
		else:
			j = md + 1
	i = 0
	j = len(a) - 1
	rf = -1
	while i >= 0 and j < len(a) and (i <= j):
		md = (i + j) // 2
		if a[md] <= r:
			i = md + 1
			rf = md
		else:
			j = md - 1
	return max(0, rf - lf + 1)

def main():
	for _ in range(get_int()):
		n = get_int()
		a = get_ints_in_list()
		lstBit = []
		for i in range(n):
			cnt = 0
			v = a[i]
			while v:
				cnt += 1
				v = v // 2
			lstBit.append(cnt)
		pref = [[] for _ in range(32)]
		for i in range(32):
			pref[i] = [0]
			for j in range(n):
				pref[i].append(pref[i][-1])
				if i + 1 == lstBit[j]:
					pref[i][-1] += 1
		zeros = [0]
		for v in a:
			zeros.append(zeros[-1])
			if v == 0:
				zeros[-1] += 1
		for _ in range(get_int()):
			(l, r, x) = get_ints_in_variables()
			if x == 0:
				print(r - l + 1 - (zeros[r] - zeros[l - 1]))
				continue
			cnt = 0
			while x:
				cnt += 1
				x = x // 2
			print(r - l + 1 - (pref[cnt - 1][r] - pref[cnt - 1][l - 1]))
main()


from sys import stdin, stdout
import math
from collections import Counter
import functools
import time

def tr():
	return range(int(line()))

def sm():
	return map(int, line().split())

def ln():
	return list(sm())

def nl():
	return int(line())

def ssm():
	return map(str, line().split())

def line():
	return stdin.readline().rstrip()

def b(x):
	return bin(x).replace('0b', '')

def o(x):
	if type(x) != type(''):
		x = str(x)
	stdout.write(x + '\n')

def osp(x):
	if type(x) != type(''):
		x = str(x)
	stdout.write(x + ' ')

def ol(x):
	stdout.write(' '.join(map(str, x)) + '\n')

def msbp(n):
	return int(math.log2(n)) + 1 if n != 0 else 0

def main():
	for _ in tr():
		n = nl()
		a = ln()
		prefix_mat = [[0] * 32 for _ in range(n + 1)]
		for i in range(n):
			pos = msbp(a[i])
			for j in range(32):
				prefix_mat[i + 1][j] = prefix_mat[i][j] + (j == pos)
		q = nl()
		for _ in range(q):
			(l, r, x) = sm()
			pos = msbp(x)
			print(r - l + 1 - (prefix_mat[r][pos] - prefix_mat[l - 1][pos]))
main()


from math import log2

def solveFast():
	x = int(log2(X)) + 1 if X != 0 else 0
	return R - L + 1 - l_sum[R][x] + l_sum[L - 1][x]
ans = []
for _ in range(int(input())):
	N = int(input())
	A = [int(log2(int(x))) + 1 if x != '0' else 0 for x in input().split()]
	old = [0] * 32
	l_sum = [list(old)]
	for i in range(N):
		old[A[i]] += 1
		l_sum.append(list(old))
	Q = int(input())
	for q in range(Q):
		(L, R, X) = [int(x) for x in input().split()]
		if L > R:
			(L, R) = (R, L)
		ans.append(solveFast())
for a in ans:
	print(a)


import math

def msb_pos(n):
	if n == 0:
		return 0
	c = 1
	while n >> c:
		c += 1
	return c
for test in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	q = int(input())
	msb_sum = [[0 for i in range(32)] for i in range(n + 2)]
	for i in range(n):
		pos = msb_pos(a[i])
		for m in range(32):
			msb_sum[i + 1][m] = msb_sum[i][m] + (m == pos)
	for i in range(q):
		(l, r, x) = map(int, input().split())
		pos = msb_pos(x)
		print(r - l + 1 - (msb_sum[r][pos] - msb_sum[l - 1][pos]))


import math

def msbp(z):
	if z == 0:
		return 0
	c = 1
	while z >> c:
		c += 1
	return c
for i in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	k = [[0 for i in range(32)] for i in range(n + 1)]
	for i in range(n):
		j = msbp(a[i])
		for m in range(32):
			k[i + 1][m] = k[i][m] + (m == j)
	q = int(input())
	for i in range(q):
		(l, r, x) = map(int, input().split())
		j = msbp(x)
		ans = r - l + 1 - k[r][j] + k[l - 1][j]
		print(ans)


def msb(n):
	ans = 0
	while n > 0:
		n >>= 1
		ans += 1
	return ans
for _ in range(int(input())):
	n = int(input())
	arr = list(map(int, input().split()))
	arr1 = [[0] * 32 for _ in range(n)]
	arr1[0][msb(arr[0])] += 1
	for i in range(1, n):
		temp = msb(arr[i])
		for j in range(32):
			arr1[i][j] = arr1[i - 1][j]
		arr1[i][temp] += 1
	q = int(input())
	for _ in range(q):
		(l, r, x) = map(int, input().split())
		temp = msb(x)
		ans = arr1[r - 1][temp] - arr1[l - 1][temp]
		if msb(arr[l - 1]) == temp:
			ans += 1
		ans = r - l + 1 - ans
		print(ans)


import math

def lg(a):
	if a == 0:
		return 31
	else:
		return math.log2(a)
t = int(input())
for _ in range(t):
	n = int(input())
	a = list(map(int, map(lg, map(int, input().split(' ')))))
	tbl = [[0 for i in range(n + 1)] for j in range(32)]
	for i in range(1, n + 1):
		for j in range(32):
			tbl[j][i] = tbl[j][i - 1]
		tbl[a[i - 1]][i] += 1
	q = int(input())
	for _ in range(q):
		(l, r, x) = map(int, input().split(' '))
		x = int(lg(x))
		print(r - l + 1 - tbl[x][r] + tbl[x][l - 1])


def msb(num):
	if num == 0:
		return num
	blk = 1
	while num >> blk:
		blk += 1
	return blk

def ans():
	ans = 0
	n = int(input())
	l = list(map(int, input().split()))
	dp = [[0 for i in range(32)] for i in range(n + 1)]
	for i in range(n):
		b = msb(l[i])
		for j in range(0, 32):
			dp[i + 1][j] = dp[i][j] + (b == j)
	q = int(input())
	for j in range(q):
		(l, r, x) = map(int, input().split())
		b = msb(x)
		ans = r - l + 1 - (dp[r][b] - dp[l - 1][b])
		print(ans)
for _ in range(int(input())):
	ans()


def msb_finder(n):
	if n == 0:
		return 0
	msb = 1
	while n >> msb:
		msb += 1
	return msb
for _ in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	mat = [[0 for i in range(32)] for i in range(n + 1)]
	for i in range(n):
		balancer = msb_finder(l[i])
		for j in range(32):
			mat[i + 1][j] = mat[i][j] + (balancer == j)
	for q in range(int(input())):
		(L, R, X) = map(int, input().split())
		x = msb_finder(X)
		print(R - L + 1 - (mat[R][x] - mat[L - 1][x]))


def msb(n):
	ans = 1
	count = 0
	while n:
		n = n >> 1
		count += 1
	return count
t = int(input())
for i in range(t):
	n = int(input())
	arr = list(map(int, input().split()))
	dp = [[0 for j in range(32)] for i in range(n + 1)]
	for i in range(n):
		res = msb(arr[i])
		for j in range(32):
			if res == j:
				dp[i + 1][j] = dp[i][j] + 1
			else:
				dp[i + 1][j] = dp[i][j]
	q = int(input())
	for j in range(q):
		(l, r, x) = [int(i) for i in input().split()]
		ans = r - l + 1 - (dp[r][msb(x)] - dp[l - 1][msb(x)])
		print(ans)


import math
for _ in range(int(input())):
	n = int(input())
	arr = list(map(int, input().split()))
	q = int(input())
	unsets = [[0 for _ in range(n)] for _ in range(32)]
	zeros = []
	for ele in arr:
		if ele != 0:
			zeros.append(1)
		else:
			zeros.append(0)
	for i in range(1, len(zeros)):
		zeros[i] += zeros[i - 1]
	for (j, ele) in enumerate(arr):
		for i in range(31, -1, -1):
			if ele & 1 << i:
				unsets[i][j] = 1
				break
	for j in range(len(unsets)):
		for i in range(1, len(unsets[j])):
			unsets[j][i] += unsets[j][i - 1]
	for _ in range(q):
		(l, r, x) = map(int, input().split())
		ans = 0
		if x == 0:
			if l - 1 == 0:
				print(zeros[r - 1])
			else:
				print(zeros[r - 1] - zeros[l - 2])
		else:
			k = int(math.log(x, 2))
			if l - 1 == 0:
				print(r - l + 1 - unsets[k][r - 1])
			else:
				print(r - l + 1 - (unsets[k][r - 1] - unsets[k][l - 2]))


import math
t = int(input())
for _ in range(t):
	n = int(input())
	a = list(map(int, input().split()))
	c = [[0] * (n + 1) for __ in range(33)]
	for (i, v) in enumerate(a, start=1):
		po = 32
		for j in range(33):
			c[j][i] = c[j][i - 1]
		if v != 0:
			po = int(math.log(v, 2))
		c[po][i] += 1
	q = int(input())
	for i in range(q):
		(l, r, x) = map(int, input().split())
		(po, l) = (32, l - 1)
		if x != 0:
			po = int(math.log(x, 2))
		print(r - l - (c[po][r] - c[po][l]))


from math import inf
from collections import *
import math, os, sys, heapq, bisect, random, threading
from functools import lru_cache
from itertools import *

def inp():
	return sys.stdin.readline().rstrip('\r\n')

def out(var):
	sys.stdout.write(str(var))

def inpu():
	return int(inp())

def lis():
	return list(map(int, inp().split()))

def stringlis():
	return list(map(str, inp().split()))

def sep():
	return map(int, inp().split())

def strsep():
	return map(str, inp().split())

def fsep():
	return map(float, inp().split())
(M, M1) = (1000000007, 998244353)

def main():
	how_much_noob_I_am = 1
	how_much_noob_I_am = inpu()
	for _ in range(how_much_noob_I_am):
		n = inpu()
		arr = lis()
		dp = [[0] * (n + 1) for i in range(32)]
		zero = [0] * (n + 1)
		for i in range(n):
			zero[i + 1] = zero[i] + int(arr[i] == 0)
		for i in range(32):
			for j in range(n):
				if len(bin(arr[j]).replace('0b', '')) == i + 1 and arr[j] != 0:
					dp[i][j + 1] = dp[i][j]
				else:
					dp[i][j + 1] = dp[i][j] + 1
		q = inpu()
		for i in range(q):
			(l, r, x) = sep()
			if x == 0:
				print(r - l + 1 - (zero[r] - zero[l - 1]))
				continue
			l -= 1
			p = len(bin(x).replace('0b', '')) - 1
			print(dp[p][r] - dp[p][l])
main()


import math

def main():
	n = int(input())
	arr = list(map(int, input().split()))
	q = int(input())
	queries = []
	for i in range(q):
		queries.append(list(map(int, input().split())))
	lsb = []
	for i in range(n):
		if arr[i] != 0:
			lsb.append(int(math.log(arr[i], 2)))
		else:
			lsb.append(-1)
	dp = [[0 for i in range(33)] for j in range(n)]
	for i in range(n):
		if i == 0:
			if lsb[i] == -1:
				dp[i][32] = -1
			else:
				dp[i][lsb[i]] = 1
		elif lsb[i] == -1:
			dp[i][32] = dp[i - 1][32] - 1
			for j in range(32):
				dp[i][j] = dp[i - 1][j]
		else:
			for j in range(33):
				dp[i][j] = dp[i - 1][j]
			dp[i][lsb[i]] += 1
	ans = []
	for q in queries:
		l = q[0] - 1
		r = q[1] - 1
		x = q[2]
		if x == 0:
			zero = abs(dp[r][32]) - abs(dp[l][32])
			if arr[l] == 0:
				zero += 1
			ans.append(r - l + 1 - zero)
		else:
			index = int(math.log(x, 2))
			total = r - l + 1
			wasted = dp[r][index] - dp[l][index]
			if arr[l] != 0:
				if index == int(math.log(arr[l], 2)):
					wasted += 1
			ans.append(total - wasted)
	return ans
t = int(input())
for i in range(t):
	ans = main()
	for e in ans:
		print(e)


import math

def func1(a, l, r, x):
	return 0
t = int(input())
for i in range(t):
	n = int(input())
	a = list(map(int, input().split(' ')))
	p = []
	temp = [0 for i in range(32)]
	p.append(temp.copy())
	for i in range(n):
		w = temp.copy()
		if a[i] != 0:
			w[math.floor(math.log2(a[i]))] += 1
		else:
			w[31] += 1
		temp = w.copy()
		p.append(w)
	q = int(input())
	for j in range(q):
		(l, r, x) = map(int, input().split(' '))
		if x != 0:
			x = int(math.log2(x))
		else:
			x = 31
		result = p[r][x] - p[l - 1][x]
		print(r - l + 1 - result)


import math
t = int(input())
for i in range(t):
	n = int(input())
	a = [int(x) for x in input().split()]
	d = [[0 for j in range(33)] for k in range(n + 1)]
	for i in range(1, n + 1):
		tp = a[i - 1]
		for j in range(33):
			d[i][j] = d[i - 1][j]
		r = 32
		if tp != 0:
			r = int(math.log(tp) / math.log(2))
		d[i][r] += 1
	q = int(input())
	for j in range(q):
		(s, h, x) = map(int, input().split())
		c = 0
		pow = 32
		if x != 0:
			pow = int(math.log(x) / math.log(2))
		c = d[h][pow] - d[s - 1][pow]
		ans = h - s + 1 - c
		print(ans)


t = int(input())
for _ in range(t):
	n = int(input())
	a = [int(x) for x in input().split()]
	q = int(input())
	pre = []
	for i in a:
		if i == 0:
			pre.append(0)
		else:
			pre.append(len(bin(i)) - 2)
	mat = []
	k = [0] * 32
	mat.append([0] * 32)
	for i in pre:
		s = [0] * 32
		s = k.copy()
		s[i] += 1
		k[i] += 1
		mat.append(s)
	for i in range(q):
		(l, r, x) = [int(x) for x in input().split()]
		k = 0
		if x != 0:
			k = len(bin(x)) - 2
		c = mat[r][k] - mat[l - 1][k]
		print(r - l + 1 - c)


import math
t = int(input())
while t > 0:
	n = int(input())
	st = input().split(' ')
	dp = [[0] * 33 for _ in range(n + 1)]
	i = 1
	for item in st:
		temp = int(item)
		j = 0
		while j < 33:
			dp[i][j] = dp[i - 1][j]
			j += 1
		pwr = 32
		if temp != 0:
			pwr = int(math.log(temp) / math.log(2))
		dp[i][pwr] += 1
		i += 1
	q = int(input())
	i = 0
	while i < q:
		(si, ei, x) = map(int, input().split())
		cnt = 0
		pwr = 32
		if x != 0:
			pwr = int(math.log(x) / math.log(2))
		cnt = dp[ei][pwr] - dp[si - 1][pwr]
		ans = ei - si + 1 - cnt
		print(ans)
		i += 1
	t -= 1


def log(x, y):
	coun = 0
	while x >= y:
		coun += 1
		x //= y
	return coun
for _ in range(int(input())):
	n = int(input())
	arr = list(map(int, input().split()))
	q = int(input())
	lst = [[0] * (n + 1) for i in range(32)]
	for i in range(1, n + 1):
		for j in range(32):
			lst[j][i] = lst[j][i - 1]
		exp = 31
		if arr[i - 1] != 0:
			exp = log(arr[i - 1], 2)
		lst[exp][i] += 1
	for i in range(q):
		(l, r, x) = list(map(int, input().split()))
		exp = 31
		if x != 0:
			exp = log(x, 2)
		coun = lst[exp][r] - lst[exp][l - 1]
		print(r - l + 1 - coun)


import math
for _ in range(int(input())):
	n = int(input())
	dd = [[0 for i in range(n + 1)] for j in range(33)]
	k = list(map(int, input().split()))
	for i in range(1, n + 1):
		temp = k[i - 1]
		for j in range(33):
			dd[j][i] = dd[j][i - 1]
		pwr = 32
		if temp != 0:
			pwr = int(math.log2(temp))
		dd[pwr][i] += 1
	for w in range(int(input())):
		(l, r, x) = map(int, input().split())
		c = 0
		pwr = 32
		if x != 0:
			pwr = int(math.log2(x))
		c = dd[pwr][r] - dd[pwr][l - 1]
		print(r - l + 1 - c)


import math
T = int(input())
for i in range(T):
	N = int(input())
	A = [int(x) for x in input().split()]
	arr = [[0 for i in range(N + 1)] for j in range(33)]
	for i in range(N):
		for j in range(33):
			arr[j][i + 1] = arr[j][i]
		if A[i] != 0:
			power = math.floor(math.log(A[i], 2))
			arr[power][i + 1] = arr[power][i] + 1
		else:
			arr[32][i + 1] = arr[32][i] + 1
	Q = int(input())
	for i in range(Q):
		(L, R, X) = [int(x) for x in input().split()]
		count = 0
		if X == 0:
			power = 32
		else:
			power = math.floor(math.log(X, 2))
		total = R - L + 1
		useless = arr[power][R] - arr[power][L - 1]
		count = total - useless
		print(count)


from math import log2
for _ in range(int(input())):
	n = int(input())
	arr = [int(x) for x in input().split()]
	comm_sums = dict()
	for i in range(31):
		comm_sums[i] = []
		c = 0
		for x in arr:
			comm_sums[i].append(c)
			if x >= 2 ** i and x < 2 ** (i + 1):
				c += 1
		comm_sums[i].append(c)
	comm_sums[-1] = []
	c = 0
	for x in arr:
		comm_sums[-1].append(c)
		if x == 0:
			c += 1
	comm_sums[-1].append(c)
	q = int(input())
	for i in range(q):
		(l, r, x) = [int(x) for x in input().split()]
		if x == 0:
			print(r - l + 1 - (comm_sums[-1][r] - comm_sums[-1][l - 1]))
			continue
		p = int(log2(x))
		print(r - l + 1 - (comm_sums[p][r] - comm_sums[p][l - 1]))


from math import log2
for _ in range(int(input())):
	n = int(input())
	nums = list(map(int, input().split()))
	checks = [0 for i in range(32)]
	d = [tuple(checks)]
	for i in range(n):
		if nums[i]:
			pwr = int(log2(nums[i]))
			checks[pwr] += 1
		else:
			checks[31] += 1
		d.append(tuple(checks))
	q = int(input())
	for i in range(q):
		(l, r, x) = map(int, input().split())
		if x:
			x = int(log2(x))
		else:
			x = 31
		print(r - l + 1 - d[r][x] + d[l - 1][x])


def top_set_bit(x):
	if x == 0:
		return int(0)
	return 1 + int(top_set_bit(x >> 1))
T = int(input())
for i in range(T):
	N = int(input())
	values = [int(i) for i in input().split()]
	for i in range(N):
		values[i] = top_set_bit(values[i])
	dp = []
	for j in range(32):
		dp.append([0])
		for i in range(N):
			dp[j].append(dp[j][i])
			if j != values[i]:
				dp[j][i + 1] += 1
	Q = int(input())
	for j in range(Q):
		(L, R, X) = map(int, input().split())
		X = top_set_bit(X)
		print(dp[X][R] - dp[X][L - 1])


import math
t = int(input())
while t > 0:
	n = int(input())
	a = input()
	a = list(a.split(' '))
	dp = [[0] * 33 for _ in range(n + 1)]
	i = 1
	while i <= n:
		temp = int(a[i - 1])
		j = 0
		while j < 33:
			dp[i][j] = dp[i - 1][j]
			j += 1
		pwr = 32
		if temp != 0:
			pwr = int(math.log(temp) / math.log(2))
		dp[i][pwr] += 1
		i += 1
	q = int(input())
	while q > 0:
		b = input()
		b = list(b.split(' '))
		c = 0
		pr = 32
		if int(b[2]) != 0:
			pr = int(math.log(int(b[2])) / math.log(2))
		c = dp[int(b[1])][pr] - dp[int(b[0]) - 1][pr]
		ans = int(b[1]) - int(b[0]) + 1 - c
		print(ans)
		q -= 1
	t -= 1


try:
	import math
	t = int(input())
	for _ in range(t):
		n = int(input())
		arr = list(map(int, input().split()))
		dp = []
		for i in range(n + 1):
			dp.append([])
			for _ in range(33):
				dp[i].append(0)
		for i in range(1, n + 1):
			temp = arr[i - 1]
			for j in range(33):
				dp[i][j] = dp[i - 1][j]
			pwr = 32
			if temp != 0:
				pwr = int(math.log(temp, 2))
			dp[i][pwr] += 1
		q = int(input())
		for i in range(q):
			(l, r, x) = map(int, input().split())
			scnt = 0
			pwr = 32
			if x != 0:
				pwr = int(math.log(x, 2))
			cnt = dp[r][pwr] - dp[l - 1][pwr]
			ans = r - l + 1 - cnt
			print(ans)
except:
	pass


try:
	from debug import debug, timer
except ImportError:
	pass
from sys import stdin
input = stdin.readline

def rii():
	return range(int(input().strip()))

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

def mii():
	return map(int, input().strip().split(' '))

def lmii():
	return list(map(int, input().strip().split(' ')))

def si():
	return str(input().strip())

def getvals():
	while True:
		yield from input().split()

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

def smallest_first(m, n):
	return (min(m, n), max(m, n))
from math import log2

def ilog(m):
	if m == 0:
		return -1
	else:
		return int(log2(m))

def solve(*args):
	(n, a, l, r, x, logs, zeros) = args
	c = 0
	if x == 0:
		c = zeros[r] - zeros[l - 1]
	else:
		log_x = ilog(x)
		c = logs[log_x][r] - logs[log_x][l - 1]
	return r - l + 1 - c

def gen_logs(n, a):
	logs = [[0 for _ in range(n + 1)] for _ in range(32)]
	zeros = [0 for _ in range(n + 1)]
	for i in range(1, n + 1):
		for j in range(32):
			logs[j][i] = logs[j][i - 1]
			zeros[i] = zeros[i - 1]
		if a[i - 1] != 0:
			logs[ilog(a[i - 1])][i] += 1
		else:
			zeros[i] += 1
	return (logs, zeros)

def do_codechef():
	for t in rii():
		n = ii()
		a = lmii()
		(logs, zeros) = gen_logs(n, a)
		q = ii()
		for _ in range(q):
			(l, r, x) = mii()
			print(solve(n, a, l, r, x, logs, zeros))
do_codechef()
exit()


def readInt():
	return int(input())

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

def readString():
	return input().rstrip()

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

def readCase():
	n = readInt()
	numbers = readInts()
	q = readInt()
	queries = [readInts() for _ in range(q)]
	return (n, numbers, q, queries)

def solve(n, numbers, q, queries):
	prefix = [[0 for _ in range(32)] for _ in range(n + 1)]
	for (pos, num) in enumerate(numbers):
		num_len = num.bit_length()
		for bit in range(32):
			if bit == num_len:
				prefix[pos + 1][bit] = prefix[pos][bit] + 1
			else:
				prefix[pos + 1][bit] = prefix[pos][bit]
	for (l, r, x) in queries:
		x_bit = x.bit_length()
		failures = prefix[r][x_bit] - prefix[l - 1][x_bit]
		print(r - l + 1 - failures)
cases = readInt()
for case in range(cases):
	solve(*readCase())


t = int(input())
for _ in range(t):
	n = int(input())
	d = [[0 for i in range(33)] for j in range(n + 1)]
	l = list(map(int, input().strip().split(' ')))
	for i in range(n):
		t = l[i]
		c = 0
		while t != 0:
			t = t // 2
			c = c + 1
		for j in range(33):
			d[i + 1][j] = d[i][j]
		d[i + 1][c] = d[i + 1][c] + 1
	k = int(input())
	for i in range(k):
		(a, b, h) = map(int, input().split(' '))
		a = a - 1
		c = 0
		while h != 0:
			h = h // 2
			c = c + 1
		ans = n - a
		print(b - a - d[b][c] + d[a][c])


import math
for _ in range(int(input())):
	n = int(input())
	dp = [[]]
	for l in range(33):
		dp[0].append(0)
	arr = [int(a) for a in input().split()]
	for i in range(1, n + 1):
		dp.append([])
		for j in range(33):
			dp[i].append(0)
			dp[i][j] = dp[i - 1][j]
		pwr = 32
		if arr[i - 1] != 0:
			pwr = int(math.log(arr[i - 1]) / math.log(2))
		dp[i][pwr] += 1
	for _ in range(int(input())):
		(si, ei, x) = [int(a) for a in input().split()]
		c = 0
		pwr = 32
		if x != 0:
			pwr = int(math.log(x) / math.log(2))
		c = dp[ei][pwr] - dp[si - 1][pwr]
		ans = ei - si + 1 - c
		print(ans)


from math import floor, log

def find_2_exp(n):
	return floor(log(n, 2))
for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	q = int(input())
	dp = [[_ for c in range(n + 1)] for r in range(33)]
	for i in range(n):
		for j in range(33):
			dp[j][i] = dp[j][i - 1]
		power = 32
		if a[i] != 0:
			power = find_2_exp(a[i])
		dp[power][i] += 1
	for _ in range(q):
		(l, r, x) = map(int, input().split())
		power = 32
		if x != 0:
			power = find_2_exp(x)
		mystical = dp[power][r - 1] - dp[power][l - 2]
		print(r - l + 1 - mystical)


import math
for _ in range(int(input())):
	n = int(input())
	A = list(map(int, input().split()))
	dp = [[0] * 33 for i in range(n + 1)]
	for i in range(1, n + 1):
		t = A[i - 1]
		for j in range(33):
			dp[i][j] = dp[i - 1][j]
		power = 32
		if t != 0:
			power = int(math.log(t) / math.log(2))
		dp[i][power] += 1
	Q = int(input())
	for i in range(Q):
		(L, R, X) = map(int, input().split())
		cnt = 0
		pwer = 32
		if X != 0:
			pwer = int(math.log(X) / math.log(2))
		cnt = dp[R][pwer] - dp[L - 1][pwer]
		print(R - L + 1 - cnt)


import math
dp = {0: 32}

def calc(num):
	val = dp.get(num, None)
	if not val:
		val = math.floor(math.log2(num))
		dp[num] = val
	return val

def pre_process(arr):
	mid = [[0] * 33 for i in range(len(arr) + 1)]
	for i in range(1, len(arr) + 1):
		mid[i] = mid[i - 1][:]
		log_num = calc(arr[i - 1])
		mid[i][log_num] += 1
	return mid
for _ in range(int(input().strip())):
	n = int(input())
	arr = list(map(int, input().strip().split(' ')))
	mem = pre_process(arr)
	for it in range(int(input().strip())):
		count = 0
		(l, r, x) = map(int, input().split(' '))
		x_log = calc(x)
		count = mem[r][x_log] - mem[l - 1][x_log]
		print(r - l + 1 - count)


import math
t = int(input())
for _ in range(t):
	n = int(input())
	A = list(map(int, input().split()))
	mat_dp = [[0 for x in range(33)] for y in range(n + 1)]
	for i in range(1, n + 1):
		temp = A[i - 1]
		for j in range(33):
			mat_dp[i][j] = mat_dp[i - 1][j]
		pwr = 32
		if temp > 0 or temp < 0:
			pwr = int(math.log(temp) / math.log(2))
		mat_dp[i][pwr] += 1
	q = int(input())
	for z in range(q):
		(l, r, x) = map(int, input().split())
		c = 0
		pwr = 32
		if x > 0 or x < 0:
			pwr = int(math.log(x) / math.log(2))
		c = mat_dp[r][pwr] - mat_dp[l - 1][pwr]
		ans = r - l + 1 - c
		print(ans)


from math import log2
import numpy as np
t = int(input())
for _ in range(t):
	n = int(input())
	a = list(map(int, input().split()))
	q = int(input())
	matrix = np.zeros((33, n))
	if a[0] == 0:
		matrix[0][0] = 1
	else:
		matrix[int(log2(a[0]) + 1)][0] = 1
	for i in range(1, n):
		if a[i] == 0:
			matrix[0][i] = matrix[0][i - 1] + 1
			matrix[1:, i] = matrix[1:, i - 1]
			continue
		curr_msb = int(log2(a[i])) + 1
		if curr_msb == 0:
			matrix[curr_msb][i] = matrix[curr_msb][i - 1] + 1
			matrix[1:, i] = matrix[1:, i - 1]
		else:
			matrix[:curr_msb, i] = matrix[:curr_msb, i - 1]
			matrix[curr_msb][i] = matrix[curr_msb][i - 1] + 1
			matrix[curr_msb + 1:, i] = matrix[curr_msb + 1:, i - 1]
	for query in range(q):
		(l, r, x) = map(int, input().split())
		if x == 0:
			if l == 1:
				ans = r - matrix[0][r - 1]
			elif l == r:
				ans = 1 - (matrix[0][r - 1] - matrix[0][l - 2])
			else:
				ans = r - l + 1 - (matrix[0][r - 1] - matrix[0][l - 2])
		else:
			check_msb = int(log2(x)) + 1
			if l == 1:
				ans = r - matrix[check_msb][r - 1]
			elif l == r:
				ans = 1 - (matrix[check_msb][r - 1] - matrix[check_msb][l - 2])
			else:
				ans = r - l + 1 - (matrix[check_msb][r - 1] - matrix[check_msb][l - 2])
		print(int(ans))


LIM = 2 * 10 ** 5 + 10

def HBIT(n):
	bit = -1
	while n:
		bit += 1
		n >>= 1
	return bit
hbitCount = [[0] * LIM for i in range(32)]
totalPos = [0] * LIM

def prep(A, N):
	for ind in range(N + 1):
		totalPos[ind] = 0
		for bit in range(32):
			hbitCount[bit][ind] = 0
	for (ind, el) in enumerate(A):
		totalPos[ind + 1] = totalPos[ind]
		if el:
			totalPos[ind + 1] += 1
			hbitCount[HBIT(el)][ind + 1] = 1
	for bit in range(32):
		for ind in range(1, N + 1):
			hbitCount[bit][ind] += hbitCount[bit][ind - 1]

def solve(L, R, X):
	if X == 0:
		return totalPos[R] - totalPos[L - 1]
	size = R - L + 1
	hbit = HBIT(X)
	sameHighBits = hbitCount[hbit][R] - hbitCount[hbit][L - 1]
	return size - sameHighBits
for case in range(int(input())):
	N = int(input())
	A = list(map(int, input().split()))
	prep(A, N)
	T = int(input())
	for i in range(T):
		(L, R, X) = map(int, input().split())
		print(solve(L, R, X))


t = int(input())
for i in range(0, t):
	n = int(input())
	myList = list(map(int, input().strip().split()))[:n]
	myProcessedData = []
	for i in range(0, 33):
		temp = []
		for j in range(0, n + 1):
			temp.append(0)
		myProcessedData.append(temp)
	for j in range(1, n + 1):
		if j == 1:
			if myList[j - 1] == 0:
				myProcessedData[32][j] += 1
			else:
				power = len(bin(myList[j - 1])[2:]) - 1
				myProcessedData[power][j] += 1
		else:
			for k in range(0, 33):
				myProcessedData[k][j] = myProcessedData[k][j - 1]
			if myList[j - 1] == 0:
				myProcessedData[32][j] += 1
			else:
				power = len(bin(myList[j - 1])[2:]) - 1
				myProcessedData[power][j] += 1
	q = int(input())
	for i in range(0, q):
		(l, r, x) = map(int, input().split())
		if x == 0:
			check = 32
			print(r - l + 1 - (myProcessedData[check][r] - myProcessedData[check][l - 1]))
		else:
			check = len(bin(x)[2:]) - 1
			res = r - l + 1 - (myProcessedData[check][r] - myProcessedData[check][l - 1])
			print(res)


import math

def lg(n):
	if n == 0:
		return 32
	return int(math.log2(n))
t = int(input())
while t:
	t -= 1
	n = int(input())
	l = list(map(int, input().split()))
	LIST = []
	arr = [0] * 33
	for i in l:
		arr[lg(i)] += 1
		LIST.append(arr.copy())
	q = int(input())
	while q:
		q -= 1
		(L, R, x) = list(map(int, input().split()))
		if L == 1:
			print(R - L + 1 - LIST[R - 1][lg(x)])
		else:
			print(R - L + 1 - (LIST[R - 1][lg(x)] - LIST[L - 2][lg(x)]))


import math

def dynamic_programming(query, dynamic_p):
	let = 32
	(inp1_l, inp2_r, inp3_x) = map(int, input().split())
	if inp3_x != 0:
		let = int(math.log(inp3_x) / math.log(2))
	var1 = dynamic_p[inp2_r][let]
	var2 = dynamic_p[inp1_l - 1][let]
	solved = var1 - var2
	return inp2_r - inp1_l + 1 - solved
testcase = int(input())
for _ in range(testcase):
	var_test = int(input())
	list_inp = list(map(int, input().split()))
	dynamic_p = [[0] * 33 for _ in range(var_test + 1)]
	for i in range(1, var_test + 1):
		temp = list_inp[i - 1]
		for j in range(33):
			dynamic_p[i][j] = dynamic_p[i - 1][j]
		let = 32
		if temp != 0:
			var1 = math.log(temp)
			var2 = math.log(2)
			let = int(var1 / var2)
		dynamic_p[i][let] += 1
	query = int(input())
	for i in range(query):
		print(dynamic_programming(query, dynamic_p))