---
# System prepended metadata

title: Đoạn con chia hết

---

# Đoạn con chia hết - SDS

## Yêu cầu:
Cho một mảng $A$ có $n$ phần tử nguyên dương, tìm **đoạn con liên tiếp** ngắn nhất có tích các phần tử chia hết cho $x$.

## Input (vào từ SDS.INP)
- Dòng đầu tiên chứa một số nguyên $t$ là số trường hợp cần xử lý ($1 \leq t \leq 30$).
- $t$ nhóm dòng sau, mỗi nhóm dòng gồm hai dòng có dạng:
    - Dòng đầu tiên chứa $n,\ x\ (1 \leq n \leq 10^5,\ 1 \leq x \leq 10^{12})$.
    - Dòng thứ hai chứa $n$ phần tử của mảng $A \ (1 \leq A_i \leq 10^{18})$.

## Output (xuất ra SDS.OUT)
Xuất ra $t$ dòng, dòng thứ $i$ là đáp án của trường hợp thứ $i$ tương ứng trong dữ liệu nhập vào:
    - In ra vị trí chỉ số bắt đầu và kết thúc của đoạn con tìm được, nếu có nhiều đoạn thỏa yêu cầu thì in đoạn có chỉ số bắt đầu nhỏ nhất.
    - Nếu không tìm được đoạn thỏa thì in **-1 -1**.

## Ví dụ:

| SDS.INP | SDS.OUT |
|---|---|
| 1<br>5 22<br>8 9 2 3 11 | 3 5 |

| SDS.INP | SDS.OUT |
|---|---|
| 2<br>4 9<br>1 2 3 4<br>3 6<br>2 3 2 | -1 -1<br>1 2 |

## Giải thích
- Trong ví dụ thứ nhất, tích $3$ phần tử liên tiếp $2 \times 3 \times 11 = 66$ chia hết cho $22$.
- Trong ví dụ thứ hai:
    - Trường hợp đầu tiên: Không tìm được đoạn thỏa yêu cầu.
    - Trường hợp thứ hai: Có hai đoạn con liên tiếp ngắn nhất thỏa là $A[1, 2]$ và $A[2, 3]$, đáp án là đoạn con $[1, 2]$ vì có chỉ số bắt đầu nhỏ nhất.

## Subtask
- $10\%$ số test tương ứng với $10\%$ số điểm có $x$ là số nguyên tố.
- $10\%$ số test tương ứng với $10\%$ số điểm có $x$ có đúng ***ba*** ước.
- $10\%$ số test tương ứng với $10\%$ số điểm có $x$ là tích của hai số nguyên tố.
- $30\%$ số test tương ứng với $30\%$ số điểm có $n \leq 2 \times 10^3,\ A_i \leq 10^9$.
- $40\%$ số test còn lại tương ứng với $40\%$ số điểm không có ràng buộc gì thêm.

