Cho một mảng gồm ~N~ số nguyên dương ~a_1,a_2,\dots,a_N~ và một số nguyên dương ~M~. Một đoạn liên tiếp ~[l,r]~ được gọi là hợp lệ nếu:

~a_l \times a_{l+1} \times \dots \times a_r~

chia hết cho ~M~.

Có ~Q~ truy vấn. Mỗi truy vấn cho hai số ~L,R~.

Với mỗi truy vấn, hãy tìm độ dài nhỏ nhất của một đoạn liên tiếp ~[l,r]~ thỏa mãn:

• ~L \leq l \leq r \leq R~;
• tích các phần tử từ ~a_l~ đến ~a_r~ chia hết cho ~M~.

Nếu không tồn tại đoạn như vậy, in ra ~-1~.

Input

• Dòng đầu gồm ba số nguyên ~N,M,Q~ ~(1 \leq N,Q \leq 2\times10^5,\ 1 \leq M \leq 10^{14})~.
• Dòng thứ hai gồm ~N~ số nguyên ~a_i~ ~(1 \leq a_i \leq 10^9)~.
• ~Q~ dòng tiếp theo, mỗi dòng gồm hai số nguyên ~L,R~ ~(1 \leq L \leq R \leq N)~.

Output

Với mỗi truy vấn, in ra:

• độ dài nhỏ nhất của một đoạn hợp lệ nằm hoàn toàn trong ~[L,R]~;
• hoặc ~-1~ nếu không tồn tại.

Sample Input

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

Sample Output

2
2
3
2
-1
2

Giới Hạn