Elearning CodePath – CTP Online Judge

Đổi số nguyên tố

GEN044

🟢 Medium #Binary Search #Combinatorics #BFS/DFS

### Thông tin chung
Tên bài toán: Đổi số nguyên tố
Tên file đầu vào: PRIMEPATH.INP
Tên file đầu ra: PRIMEPATH.OUT

### Bài toán
Cho hai số nguyên tố A và B đều có 4 chữ số.

Mỗi bước, bạn được phép thay đổi đúng một chữ số của số hiện tại sao cho số mới tạo thành vẫn là một số nguyên tố có 4 chữ số và không chứa chữ số 0 ở đầu.

Yêu cầu: Tìm số bước ít nhất để biến đổi từ số A thành số B.

### Định dạng đầu vào
Dữ liệu vào từ file PRIMEPATH.INP:
- Dòng đầu tiên chứa số nguyên T là số lượng bộ test.
- T dòng tiếp theo, mỗi dòng chứa hai số nguyên dương A và B cách nhau bởi dấu cách.

### Giới hạn
- 1 <= T <= 100.
- A và B là các số nguyên tố có 4 chữ số (1000 <= A, B <= 9999).

### Định dạng đầu ra
Ghi ra file PRIMEPATH.OUT:
- Với mỗi bộ test, in ra một số nguyên duy nhất là số bước biến đổi ít nhất. 
- Nếu không thể biến đổi, in ra -1.

### Ví dụ
| PRIMEPATH.INP | PRIMEPATH.OUT |
| :--- | :--- |
| 1 <br> 1033 8179 | 6 |

Giải thích: 
1033 -> 1733 -> 3733 -> 3739 -> 3779 -> 8779 -> 8179.

✅ Đã AC: 3 / 4 submissions