"Thời gian là một dòng chảy miên man bất tận, nhưng giữa muôn vàn khoảnh khắc bình dị của đời người, luôn tồn tại những ngày mang vẻ đẹp nguyên sơ và độc bản — nơi mà cả Ngày lẫn Tháng đều e ấp mang trên mình tấm áo của 'Số Nguyên Tố'."

Trong một lần ngẫu hứng xách balo lên và đi du ngoạn sang xứ sở Ethiopia huyền bí, thi sĩ công nghệ Q bất ngờ phát hiện ra một bộ lịch kỳ lạ. Ở vùng đất này, một năm không phải 12 tháng như thường lệ, mà kéo dài tới 13 tháng:

• Từ tháng 1 đến tháng 12: mỗi tháng dịu dàng tròn trĩnh đúng 30 ngày.
• Riêng tháng 13: "vội dọn dẹp" kết thúc chỉ sau 5 ngày vỏn vẹn (từ ngày 1 đến ngày 5).
• Tuyệt nhiên, người dân nơi đây nói "KHÔNG" với năm nhuận để tránh gây trầm cảm cho các lập trình viên.

Vốn là một tâm hồn yêu Văn học nhưng lại lỡ "phải lòng" Toán học, Q tự tay định nghĩa khái niệm "Ngày Nguyên Tố" như một chuẩn mực của sự hoàn hảo:

Một ngày dd/mm/yyyy chỉ được công nhận là Ngày Nguyên Tố khi và chỉ khi cả Ngày (dd) lẫn Tháng (mm) đều là các số nguyên tố.

Chẳng hạn như ngày 13/07/2008.

Nhắc lại: Số nguyên tố là số tự nhiên lớn hơn 1, chỉ chia hết cho 1 và chính nó.

Lưu ý rằng, giá trị Năm (yyyy) không cần phải là số nguyên tố, số nào cũng được Q hoan hỷ đón nhận!

Đang đứng giữa ngã tư đường của quá khứ và tương lai, vũ trụ liên tục dội xuống đầu Q tới T = 10⁶ câu hỏi.

Với mỗi mốc thời gian X được đưa ra, bạn hãy viết một chương trình giúp Q giải tỏa nỗi niềm:

• Tìm ra Ngày Nguyên Tố gần nhất diễn ra trước ngày X.
• Tìm ra Ngày Nguyên Tố gần nhất diễn ra sau ngày X.

Dữ liệu vào (Input)

• Dòng đầu tiên chứa một số nguyên T (1 ≤ T ≤ 10⁶) — số lượng câu hỏi mà vũ trụ dành cho Q.
• T dòng tiếp theo, mỗi dòng chứa một mốc thời gian X theo định dạng dd/mm/yyyy, trong đó:
  • dd là 2 chữ số biểu diễn Ngày (D).
  • mm là 2 chữ số biểu diễn Tháng (M).
  • yyyy là 4 chữ số biểu diễn Năm (Y).

Dữ liệu bảo đảm luôn tồn tại Ngày Nguyên Tố ở cả trước và sau mốc thời gian X.

Dữ liệu ra (Output)

Với mỗi truy vấn trong T câu hỏi, in ra 2 dòng:

• Dòng 1: Ngày nguyên tố gần nhất diễn ra trước ngày X (định dạng dd/mm/yyyy).
• Dòng 2: Ngày nguyên tố gần nhất diễn ra sau ngày X (định dạng dd/mm/yyyy).

Ví dụ mẫu (Example)

Test 1

Input:

2
07/07/0777
03/13/1234

Output:

05/07/0777
11/07/0777
02/13/1234
05/13/1234

Ghi chú

• Truy vấn đầu tiên: Ngày 07/07 có ngày 7 và tháng 7 đều là số nguyên tố. Lùi ngày gặp 05/07 (nguyên tố), tiến lên gặp 11/07 (nguyên tố). Dễ như ăn kẹo!
• Truy vấn thứ hai: Tháng 13 là số nguyên tố (chuẩn bài!). Ngày 3 lùi lại gặp ngày 2 (nguyên tố), tiến lên gặp ngày 5 (nguyên tố).

Thang điểm & Phân loại Subtask (Scoring)

Thử thách được chia thành 5 chặng đường để thử thách tay nghề thuật toán:

• Subtask 1 — (15% số điểm): T = 1 và mốc thời gian rơi vào tháng M = 13.
• Subtask 2 — (20% số điểm): T ≤ 100, Ngày D ∈ {29, 30} và Tháng M ≥ 3.
• Subtask 3 — (20% số điểm): T ≤ 1000 và mốc thời gian thuộc tháng M ∈ {1, 2}.
• Subtask 4 — (25% số điểm): T ≤ 10⁴, không có ràng buộc gì thêm.
• Subtask 5 — (20% số điểm): T ≤ 10⁶, xử lý trơn tru siêu dữ liệu mà không dính TLE!