Mojtba has an array $a$ with $n$ elements and an integer $k$. Arpa has $q$ query in type $[L, R]$, for $i$-th query print the length of the shortest segment $[x, y] \in [L_i, R_i]$, such that $k | \prod_{j=x}^y a_j$.

Input Format

The first line of input will contain three integers, $n, k, q$ ($1 \le n, q \le 5 \cdot 10^5$, $1 \le k \le 10^9$).

Next line will contain $n$ integers $a_{1}, a_{2}, a_{3},...,a_{n}$ - integers of the array $a$ ($1 \le a_i \le 10^9$).

In $i$-th line of the next $q$ lines, two integers given, $L_i, R_i$ ($1 \le L_i \le R_i \le n$).

Output Format

For each query print the length of the shortest segment $[x, y] \in [L, R]$, such that $k | \prod_{i=x}^y a_i$. If there is no segment satisfying the condition, print $-1$.