Cho số nguyên dương N, không có chữ số nào bằng 0. Gọi k là số chữ số trong N. Chúng ta muốn lập một bội số của 3 bằng cách xóa ít nhất 0 và nhiều nhất k−1 chữ số khỏi N và nối các chữ số còn lại mà không thay đổi thứ tự. Xác định xem có thể tạo bội số của 3 theo cách này không. Nếu có thể, hãy tìm số chữ số ít nhất cần phải xóa để tạo thành một số như vậy.

Hạn chế

• 1≤ N ≤ 10¹⁸
• Không có chữ số nào trong N là 0.

  Đầu vào

Đầu vào được cung cấp từ Đầu vào tiêu chuẩn ở định dạng sau:

N

Đầu ra

Nếu không thể tạo thành bội số của 3, hãy in -1; mặt khác, in số chữ số tối thiểu phải được xóa để tạo thành một số như vậy.

Vật mẫu