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