Problem 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.

1
3
2 3 3
1
1 3

2