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

```python

USER_FILENAME = "<user_code>"
import sys, json, builtins
import math, heapq, bisect, itertools, functools, collections, statistics, fractions, decimal, operator, array, random, re, string, os, pathlib
try:
    import resource as _res
except Exception:
    _res = None
from collections import Counter, defaultdict, deque, OrderedDict
from functools import lru_cache, reduce
from itertools import accumulate, permutations, combinations, product
from math import gcd, ceil, floor, sqrt
from decimal import Decimal
try:
    from typing import *
except Exception:
    pass
try:
    sys.setrecursionlimit(1_000_000)
except Exception:
    pass
try:
    import site as _site
    try:
        _sys_sites = _site.getsitepackages() if hasattr(_site, "getsitepackages") else []
        for _p in _sys_sites:
            if _p and _p not in sys.path:
                sys.path.append(_p)
    except Exception:
        pass
    try:
        _usp = _site.getusersitepackages()
        if isinstance(_usp, str):
            _usp = [_usp]
        for _p in _usp:
            if _p and _p not in sys.path:
                sys.path.append(_p)
    except Exception:
        pass
except Exception:
    pass

ns = {"__name__": "__main__"}
for _k, _v in list(globals().items()):
    if not _k.startswith("_"):
        ns[_k] = _v
_CODE = "# cook your dish here\nimport sys\ndef get_ints(): return map(int, sys.stdin.readline().strip().split())\ndef get_list(): return list(map(int, sys.stdin.readline().strip().split()))\ndef get_list_string(): return list(map(str, sys.stdin.readline().strip().split()))\ndef get_string(): return sys.stdin.readline().strip()\ndef get_int(): return int(sys.stdin.readline().strip())\ndef get_print_int(x): sys.stdout.write(str(x) + '\\n')\ndef get_print(x): sys.stdout.write(x + '\\n')\n\ndef solve():\n    for _ in range(get_int()):\n        n = get_int()\n        arr = get_list()\n        pre = [0]*n\n        pre[0] = arr[0]\n        for i in range(1,n):\n            pre[i] = pre[i-1] + arr[i]\n        q = get_int()\n        while(q):\n            s,e = get_ints()\n            s -= 1\n            e -= 1\n            if(s == 0):\n                get_print_int(pre[e])\n            else:\n                get_print_int(pre[e] - pre[s-1])\n            q -= 1\nsolve()"
_co = compile(_CODE, USER_FILENAME, "exec")
exec(_co, ns, ns)

```

Measured memory_bytes: 15065