Elearning CodePath – CTP Online Judge

CMATUS X MINHTPC HỌC EUCLID

G62489

🟢 Medium

Không lâu trước đây, Camtus  đã học được thuật toán Euclid để tìm **ước chung lớn nhất (GCD)** của hai số.  
Ước chung lớn nhất của hai số $a$ và $b$ là số lớn nhất chia hết cho cả $a$ và $b$.

Với kiến thức này, Camtus có thể giải được một bài toán mà trước đây cô ấy chưa làm được.

MINHTPC có một bảng gồm $n$ hàng và $m$ cột, trong đó số nguyên $a_{i,j}$ nằm tại giao điểm của hàng thứ $i$ và cột thứ $j$.  
Camtus muốn đi từ **ô trên cùng bên trái** (giao điểm hàng 1, cột 1) đến **ô dưới cùng bên phải** (giao điểm hàng $n$, cột $m$), đồng thời tìm **ước chung lớn nhất của tất cả các số nằm trên đường đi**.

Camtus **chỉ được phép di chuyển xuống dưới hoặc sang phải**.  
Cô ấy đã thử nhiều đường đi khác nhau và thu được các giá trị GCD khác nhau. Camtus muốn biết **giá trị GCD lớn nhất có thể đạt được**.

Do mệt mỏi với việc tự tính toán do bói bài Tarot tình yêu quá nhiều , Camtus nhờ bạn giúp tìm **GCD lớn nhất của các số trên một đường đi hợp lệ từ ô trên cùng bên trái đến ô dưới cùng bên phải**.

---

### Input

- Dòng đầu tiên chứa số nguyên $t$ — số lượng test.

- Với mỗi test:
  - Dòng đầu tiên chứa hai số nguyên $n, m$ — số hàng và số cột của bảng.
  - $n$ dòng tiếp theo, dòng thứ $i$ chứa $m$ số nguyên $a_{i,j}$ — giá trị tại ô hàng $i$, cột $j$.

---

### Output

- Với mỗi test, in ra **một số nguyên** là **giá trị GCD lớn nhất có thể** trên một đường đi hợp lệ từ ô $(1,1)$ đến ô $(n,m)$.

---

### Ràng buộc

- $1 \le t \le 10^4$
- $1 \le n, m \le 100$
- $1 \le a_{i,j} \le 10^6$
- Tổng $n \cdot m$ của tất cả các test **không vượt quá** $2 \cdot 10^5$

---

### Ví dụ

**Input**

3
2 3
30 20 30
15 25 40
3 3
12 4 9
3 12 2
8 3 12
2 4
2 4 6 8
1 3 6 9

**Output**

10
3
1

✅ Đã AC: 2 / 4 submissions