# Function

Time Limit: 7000/3500 MS (Java/Others)

Memory Limit: 262144/262144 K (Java/Others)

## Description

The shorter, the simpler. With this problem, you should be convinced of this truth.

You are given an array $A$ of $N$ postive integers, and $M$ queries in the form $(l, r)$. A function $F(l, r)\ (1\le l \le r \le N)$ is defined as:
$F(l,r)=\left\{\begin{matrix} A_{l}&l=r; \\ F(l, r-1)\ mod A_{r}& l<r. \end{matrix}\right.$
You job is to calculate $F(l, r)$, for each query $(l, r)$.

## Input

There are multiple test cases.

The first line of input contains a integer $T$, indicating number of test cases, and $T$ test cases follow.

For each test case, the first line contains an integer $N (1\le N \le 100000)$.
The second line contains $N$ space-separated positive integers: $A_{1},\dots, A_{N}\ (0\le A_{i} \le 10^9)$.
The third line contains an integer $M$ denoting the number of queries.
The following $M$ lines each contain two integers $l, r \ (1 \le l \le r \le N)$, representing a query.

## Output

For each query$(l, r)$, output $F(l, r)$ on one line.

## Sample Input

1
3
2 3 3
1
1 3

## Sample Output

2

wange2014

## Source

2016 ACM/ICPC Asia Regional Dalian Online