Dòng sông

Thuở xa xưa, người Ai Cập tin rằng Sông Nile là món quà của các vị thần sáng thế, mang sự sống đến vùng hạ lưu màu mỡ.

Một ngày nọ, một nhà khảo cổ trẻ tuổi tìm được tấm bản đồ cổ ghi lại vị trí của một kho báu bí ẩn. Trên bản đồ chỉ xuất hiện một xâu ký tự gồm chữ cái và chữ số, khiến việc giải mã trở nên vô cùng khó khăn. Nhà khảo cổ trẻ tuổi ấy đã quyết định nhờ đến bạn - một chuyên gia trong ngành khảo cổ học. Bạn đã xem qua và nhận thấy rằng muốn giải mã tấm bản đồ này rất khó khăn. Bỗng bạn nhớ tới lời dặn lúc ra đi của sư phụ: "Nếu con gặp khó khăn, hãy mở chiếc rương dưới giường thầy", bạn mở và phát hiện một phương pháp giải mã mà sư phụ đã nghiên cứu ra.

Phương pháp ấy được tóm tắt như sau:

• Tách xâu thành các đoạn con liên tiếp chỉ gồm chữ số, sao cho mỗi đoạn là dài nhất có thể
  (tức là hai đầu đoạn không thể mở rộng thêm bằng chữ số).

• Với mỗi số:

• Ta loại bỏ toàn bộ chữ số 0 ở đầu (nếu có).

• Nếu sau khi loại bỏ thu được số mới là số nguyên tố ta sẽ giữ những số \(\le5\times10^6\).

• Với mỗi số nguyên tố, lấy số đó chia dư cho 4. Tính tổng tất cả các phần dư đó.

• Lấy tổng ở bước 3 chia dư cho 2.

Ngay lúc quan trọng nhất tờ giấy đã bị thiếu mất 1 phần do để quá lâu đã mục nát. Bỗng bạn nhớ đến một câu nói đã ghi trên bức tượng Pharaoh.

Trên đó người ta ghi lại rằng kho báu chắc chắn chỉ có thể giấu ở 2 nơi:

• Kim tự tháp Giza
• Dưới dòng sông Nile

Nếu tổng đó chia dư cho 2 ta được phần dư là 1, hãy in ra 1 (Kim tự tháp Giza), ngược lại hãy in ra 2 (Dưới dòng sông Nile).

Input

• Một dòng duy nhất chứa xâu S
• 1 ≤ |S| ≤ 10^5, xâu gồm 26 chữ cái Latin và các chữ số

Output

• In ra kết quả của bài toán (1 hoặc 2)

Example

abc0023xyz17

2

Scoring

Subtask 1 (30 points): \(1 \le |S| \le 100\)
Subtask 2 (70 points): \(1 \le |S| \le 10^5\)