The land of Programmers Army is surrounded by many islands. A unique number is associated with each island. The king of the islands is a very generous person, he donates a certain amount of gold coins to travelers for visiting each island that they visited to.
Now, you are appointed as a traveler, who will travel to all these(or some) islands as many times as the Army wants, and you will collect gold coins from the king of the island.
In each trip, you will be asked to give the total sum of gold coins you have collected.

-----Input:-----
- The first line of the input contains a single integer $T$. $T$ denoting the number of test cases. The description of $T$ test cases is as follows.
- The next line of the input contains a single integer $N$. $N$ denotes the total number of Islands.
- The next line of the input contains $N$ space-separated integers $A1, A2, A3...An$ where $ith$ number denotes the maximum number of coins that the king of $ith$ island can donate.
- Next line contains a single integer $Q$. $Q$ denotes the total number of times traveler have to go for the trip.
- Next $Q$ lines contains, two space-separated integers $Q1,Q2$ denoting the start and end number of islands, i.e. traveler will start the trip from $Q1th$ island and will go till $Q2th$ island, in each trip.
Note: islands are numbered from $1$ to $N$.

-----Output:-----
- For each trip print the total number of gold coins, traveler will collect(each on a new line).

-----Constraints:-----
- $1 \leq T \leq 100$
- $1 \leq N \leq 10^4$
- $1 \leq A1, A2, A3...An \leq 10^5$
- $1 \leq Q \leq 10^3$
- $1 \leq Q1,Q2 \leq N$

-----Sample Input:-----
1
4
10 2 5 50
2
1 3
2 4

-----Sample Output:-----
17
57

-----Explanation:-----
- 
In 1st Trip, traveler will go from 1st Island to 3rd Island, hence the total number of coins traveler can collect is 10+2+5 = 17
- 
In 2 d Trip, traveler will go from 2nd Island to 4th Island, hence the total number of coins traveler can collect is 2+5+50 = 57

Difficulty: UNKNOWN_DIFFICULTY

Starter code:

Solutions:
for i in range(int(input())):
	N = int(input())
	l = list(map(int, input().split()))
	for j in range(int(input())):
		(q1, q2) = map(int, input().split())
		temp = l[q1 - 1:q2]
		print(sum(temp))


for _ in range(int(input())):
	n = int(input())
	arr = [int(k) for k in input().split()]
	q = int(input())
	for i in range(q):
		route = [int(k) for k in input().split()]
		sum = 0
		for j in range(route[0] - 1, route[1]):
			sum = sum + arr[j]
		print(sum)


for i in range(int(input())):
	n = int(input())
	arr = list(map(int, input().split()[:n]))
	k = int(input())
	for j in range(k):
		(s, e) = list(map(int, input().split()))
		su = sum(arr[s - 1:e])
		print(su)


for _ in range(int(input())):
	a = input()
	l = list(map(int, input().split()))
	q = int(input())
	r = []
	for i in range(q):
		(a, b) = list(map(int, input().split()))
		print(sum(l[a - 1:b]))


ncases = int(input())
for cases in range(ncases):
	islands = int(input())
	pricelist = list(map(int, input().split()))
	if len(pricelist) != islands:
		continue
	visits = int(input())
	for k in range(visits):
		step = list(map(int, input().split()))
		print(sum(pricelist[step[0] - 1:step[1]]))


t = int(input())
for i in range(t):
	n = int(input())
	lst = list(map(int, input().split()))
	q = int(input())
	for j in range(q):
		(q1, q2) = list(map(int, input().split()))
		sum = 0
		for k in range(q1 - 1, q2):
			sum += lst[k]
		print(sum)


T = int(input())
for no in range(T):
	N = int(input())
	A = list(map(int, input().split()))
	Q = int(input())
	for q in range(Q):
		Q1 = list(map(int, input().split()))
		s = 0
		for i in range(Q1[0] - 1, Q1[1]):
			s += A[i]
		print(s)


def c(data):
	(n, a, q, q_i) = data
	res = []
	for (s, e) in q_i:
		res.append(str(sum(a[s - 1:e])))
	return '\n'.join(res)

def l():
	r = []
	for _ in range(int(input())):
		n = int(input())
		a = [int(x) for x in input().split()]
		q = int(input())
		q_i = [tuple([int(x) for x in input().split()]) for _ in range(q)]
		r.append((n, a, q, q_i))
	return r

def __starting_point():
	print('\n'.join(map(c, l())))
__starting_point()


for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	q = int(input())
	for i in range(q):
		(x, y) = map(int, input().split())
		ans = sum(a[x - 1:y])
		print(ans)


for _ in range(int(input())):
	n = int(input())
	arr = list(map(int, input().split()))
	for _ in range(int(input())):
		(start, end) = map(int, input().split())
		print(sum(arr[start - 1:end]))


try:
	for t in range(int(input())):
		k = int(input().strip(' '))
		kc = input().split(' ')
		for q in range(int(input())):
			(q1, q2) = input().split(' ')
			q1 = int(q1)
			q2 = int(q2)
			sum = 0
			for i in range(q1 - 1, q2):
				sum = sum + int(kc[i].strip())
			print(sum)
except EOFError as e:
	pass


t = int(input())
w = []
for i in range(t):
	n = int(input())
	a = list(map(int, input().split()))
	Q = int(input())
	for j in range(Q):
		q = list(map(int, input().split()))
		count = 0
		for k in range(q[0], q[1] + 1):
			count += a[k - 1]
		w.append(count)
for i in w:
	print(i)


try:
	n = int(input())
	for i in range(n):
		m = int(input())
		l = list(map(int, input().split()))
		q = int(input())
		for j in range(q):
			(a, b) = list(map(int, input().split()))
			newlist = l[a - 1:b]
			print(sum(newlist))
except e:
	pass


t = int(input())
for x in range(t):
	n = int(input())
	arr = input().split()
	for i in range(len(arr)):
		arr[i] = int(arr[i])
	q = int(input())
	for y in range(q):
		s = input().split()
		q1 = int(s[0]) - 1
		q2 = int(s[1]) - 1
		print(sum(arr[q1:q2 + 1]))


for i in range(int(input())):
	nlands = int(input())
	maxcoins = list(map(int, input().split()))
	for j in range(int(input())):
		trips = list(map(int, input().split()))
		print(sum(maxcoins[trips[0] - 1:trips[1]]))


from sys import stdin
for _ in range(int(stdin.readline())):
	n = int(stdin.readline())
	arr = list(map(int, stdin.readline().split()))
	for i in range(int(stdin.readline())):
		(a, b) = list(map(int, stdin.readline().split()))
		print(sum(arr[a - 1:b]))


testcases = int(input())
for _ in range(testcases):
	total_islands = int(input())
	coins_list = list(map(int, input().split()))
	total_trips = int(input())
	for _ in range(total_trips):
		coins = 0
		(start, end) = list(map(int, input().split()))
		for i in range(start - 1, end):
			coins = coins + coins_list[i]
		print(coins)


T = int(input())
for _ in range(T):
	a = int(input())
	b = list(map(int, input().split()))
	c = int(input())
	for _ in range(c):
		d = list(map(int, input().split()))
		e = d[0] - 1
		print(sum(b[e:d[1]]))


import sys

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

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

def get_list_string():
	return list(map(str, sys.stdin.readline().strip().split()))

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

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

def get_print_int(x):
	sys.stdout.write(str(x) + '\n')

def get_print(x):
	sys.stdout.write(x + '\n')

def solve():
	for _ in range(get_int()):
		n = get_int()
		arr = get_list()
		pre = [0] * n
		pre[0] = arr[0]
		for i in range(1, n):
			pre[i] = pre[i - 1] + arr[i]
		q = get_int()
		while q:
			(s, e) = get_ints()
			s -= 1
			e -= 1
			if s == 0:
				get_print_int(pre[e])
			else:
				get_print_int(pre[e] - pre[s - 1])
			q -= 1
solve()


try:

	def fun(N, coins, q1, q2):
		arr = coins[q1 - 1:q2]
		return sum(arr)
	T = int(input())
	for _ in range(T):
		N = int(input())
		coins = [int(i) for i in input().split()]
		q = int(input())
		for i in range(q):
			(q1, q2) = list(map(int, input().split()))
			print(fun(N, coins, q1, q2))
except:
	pass


t = int(input())
result = []

def logic(arr, p1, p2):
	return sum(arr[p1 - 1:p2])
for i in range(0, t):
	n = int(input())
	arr = list(map(int, input().split()))
	q = int(input())
	for x in range(0, q):
		(p1, p2) = list(map(int, input().split()))
		result.append(logic(arr, p1, p2))
for item in result:
	print(item)