BÀI 1: MẬT MÃ KÉT SẮT

• Pitomon đã xâm nhập thành công vào phòng lưu trữ cốt lõi. Tại đây, một chiếc két sắt chứa bí mật quốc gia đang được bảo vệ bởi một hệ thống mã hóa cổ đại vô cùng nghiêm ngặt.

• Màn hình hệ thống hiện lên một cuộn dữ liệu nhiễu loạn là một xâu S gồm các chữ cái in thường và chữ số. Để mở được chiếc két sắt, Pitomon phải trích xuất được các "Mật mã lõi" (hay còn gọi là các Số Đặc Biệt) ẩn giấu trong đó. Các ký tự chữ số liên tiếp trong S sẽ tạo thành các số nguyên dương. Một số nguyên X được coi là "Số Đặc Biệt" nếu nó thỏa mãn đồng thời hai điều kiện sau:

• Số lượng ước số nguyên dương của X là một số lẻ.

• Tổng các chữ số của X là một số nguyên tố.

• Chú ý: Các chuỗi chữ số được trích xuất có thể có chữ số 0 ở đầu, giá trị của nó vẫn được tính bình thường nhưng tổng chữ số phải tính bao gồm cả các chữ số 0 đó. Các điều kiện này chính là màng lọc an ninh mà Pitomon cần vượt qua. Các bạn hãy giúp anh ấy viết một tool giải mã thật nhanh chóng để lấy được mật mã trước khi còi báo động vang lên nhé!

Input

• Một dòng duy nhất chứa xâu S gồm các chữ cái in thường tiếng Anh và các chữ số (0-9).

Output

• In ra tất cả các "Số Đặc Biệt" được trích xuất từ xâu S theo đúng thứ tự xuất hiện, mỗi số trên một dòng (nếu một số xuất hiện nhiều lần thì in ra bấy nhiêu lần). Nếu không tìm thấy Số Đặc Biệt nào, không in ra gì cả.

Scoring

• Subtask 1: có 40% số điểm với độ dài xâu S <= 1000, các số tạo thành không vượt quá 10^6.
• Subtask 2: có 60% số điểm với độ dài xâu S <= 10^6, các số tạo thành không vượt quá 10^12.

Sample Input 1

a16bc12d004e49f7g025

Sample Output 1

16
49
025

Sample Input 2

pitomon289is144the00049best100

Sample Output 2

289
00049

Giải thích

Ở ví dụ thứ nhất, hệ thống trích xuất được các số là: 16, 12, 004, 49, 7, 025.

- Số 16: Số lượng ước số là 5 -> Lẻ. Tổng chữ số: 7 (số nguyên tố) -> Thỏa mãn.
- Số 12: Số lượng ước số là 6 -> Chẵn -> Không thỏa mãn.
- Số 004: Giá trị là 4. Số lượng ước số là 3 -> Lẻ. Tổng chữ số: 4 (không là số nguyên tố) -> Không thỏa mãn.
- Số 49: Giá trị là 49. Số lượng ước số là 3 -> Lẻ. Tổng chữ số: 13 (số nguyên tố) -> Thỏa mãn.
- Số 7: Số lượng ước số là 2 -> Chẵn -> Không thỏa mãn.
- Số 025: Giá trị là 25. Số lượng ước số là 3 -> Lẻ. Tổng chữ số: 7 (số nguyên tố) -> Thỏa mãn.