Steve trưc nhật vì vậy hôm nay bạn đến trường sớm, giặt khăn lau bảng và xóa bảng. Đang xóa bỗng Steve nhận thấy dãy số mà mình đã xóa một phần khá đặc biệt, phần đầu của nó là

1 2 3 2 3 4 3 4 5 4 5 6 5 6 7

Đáng tiếc, phần còn lại của dãy đã bị xóa mất. Cuối cùng Steve cũng xóa xạch bảng trước khi trống vào lớp vang lên, nhưng dãy số trên vẫn cứ lởn vởn mãi trong đầu.

Buổi tối, khi lên giường ngủ, Steve lại nghĩ về dãy số này. Steve nhận thấy số 1 xuất hiện 1 lần trong dãy, số 2 xuất hiện 2 lần và lần đầu ở vị trí thứ 2, số 3 xuất hiện 3 lần và lần đầu ở vị trí thứ 3, nhưng số 4 thì lần đầu tiên xuất hiện không ở vị trí thứ 4. Tổng quát hơn số k sẽ xuất hiện lần đầu ở vị trí thứ mấy trong dãy.

Bạn có thể giúp Steve tìm ra vị trí xuất hiện đầu tiên của số nguyên k(k<=1 tỷ) trong dãy không?

VD: NUM25.inp :5

NUM25.out :9

vậy vị trí xuất hiện đầu tiên của 5 trong dãy số đó là 9

-Cho số n ở hệ cơ số 10, có không quá 20 chữ số và không chứa các số 0 không có nghĩa ở đầu. Bằng cách xóa một hoặc một vài chữ số liên tiếp của n (nhưng không xóa hết tất cả các chữ số của n) ta nhận được những số mới. Số mới được chuẩn hóa bằng cách xóa các chữ số 0 vô nghĩa nếu có. Tập số nguyên D được xây dựng bằng cách đưa vào nó số n, các số mới khác nhau đã chuẩn hóa và khác n. Ví dụ, với n = 1005 ta có thể nhận được các số mới như sau:

♦ Bằng cách xóa một chữ số ta có các số: 5 (từ 005), 105, 105, 100;

♦ Bằng cách xóa hai chữ số ta có các số: 5 (từ 05), 15, 10;

♦ Bằng cách xóa 3 chữ số ta có các số: 5 và 1.

-Tập D nhận được từ n chứa các số {1005, 105, 100, 15, 10, 5, 1}. Trong tập D này có 3 số chia hết cho 3, đó là các số 1005, 105 và 15.

-Yêu cầu: Cho số nguyên n. Hãy xác định số lượng số chia hết cho 3 có mặt trong tập D được tạo thành từ n.

-Dữ liệu: Vào từ file văn bản NUMSET.INP gồm một dòng chứa số nguyên n.

- Kết quả: Đưa ra file văn bản NUMSET.OUT một số nguyên – số lượng số chia hết cho 3 tìm được.

VD: dayso.inp:5

dayso.out:9