Cho một số tự nhiên ~N > 1~ (~1 < N < 10^{7}~). Tìm số K là số nguyên tố không vượt quá N trong các trường hợp sau:

1. K có chữ số tạn cùng lớn nhất. Nếu có nhiều số như vậy, lấy số lớn nhất
2. K có tổng các chữ số chia hết cho 5. Nếu có nhiều số như vậy, lấy số lớn nhất.
3. K có các chữ số đều là số nguyên tố ~(2, 3, 5, 7)~. Nếu có nhiều số như vậy, lấy số lớn nhất.

Dữ liệu vào: Một số nguyên ~N~ (~1 < N < 10^{7}~)

Dữ liệu ra: Số K tương ứng với các trường hợp trên

Sample Input

100

Sample Output

89 73 73

Giải thích:

• 89 là số nguyên tố lớn nhất có tận cùng là số 9.
• 73 là số nguyên tố lớn nhất có tổng chữ số bằng 10 và chia hết cho 5
• 73 là số nguyên tố mà các chữ số của nó đều là số nguyên tố

subtask

• Subtask 1 (30 điểm): 1 ≤ N ≤ ~10^4~

• Subtask 2 (40 điểm): 1 ≤ N ≤ ~10^5~

• Subtask 3 (30 điểm): 1 ≤ N ≤ ~10^7~