Finally comes the marathon day. The track has several checkpoints. You are given i values where ith value (0 based indexing) denotes the distance between the ith and (i-1)th checkpoint. The first value (0th checkpoint) is the distance between start point and 0th checkpoint. The second value (1st checkpoint) is the distance between (0th and 1st checkpoint) and so on.

For smooth organisation the core team requires distances between several checkpoints. The core team gives you several queries in the form of 2 checkpoint numbers (0-based). Answer the distance between the given checkpoint numbers.

Input:

The first line contains an integer T, the number of test cases. Then T test cases follow.

A single test case consists of:

An integer n, which is the number of checkpoints.

In the next line d0, d1, d2, ......, dn-1 values follow as described above.

In the next line an integer q, which is the number of queries.

q lines follow, each line containing two checkpoint numbers a and b.

There is a blank line after each test case in the input.

Output:

For each test case, print q lines each containing the distance between the 2 checkpoints.

Constraints:

1 <= T <= 20

1 <= n <= 100000

0 <= di <= 1000000000

0 <= a <= b < n

1 <= q <= 100000