You are given a sequence of length $n$ and $m$ query operations.

Each query provides parameters $l, r, b$. You need to output the maximum $x$ such that there exists an $a$ satisfying $0 \leq a < b$, where $a, a+b, a+2b, \ldots, a+(x-1)b$ all appear at least once in the interval $[l, r]$.

If no such number exists in $[0, b-1]$, output $0$.

Input

The first line contains an integer $n$.

The second line contains $n$ integers representing the sequence.

The third line contains an integer $m$.

The following $m$ lines each contain three integers $l, r, b$, representing a query operation.

Output

For each query, output a single integer on a new line representing the answer.

Examples

Input 1

6
1 1 4 5 1 4
3
1 6 1
2 3 3
3 4 1

Output 1

0
2
0

Note

Idea: nzhtl1477, Solution: nzhtl1477, Code: ccz181078, Data: ccz181078 & Forever_Pursuit

For $30\%$ of the data, all numbers that appear are in the range $[0, 1000]$.

For another $30\%$ of the data, $b \leq 1000$.

For $100\%$ of the data, all numbers that appear are in the range $[0, 10^5]$.