Hãy xác định tất cả các cách xoá như trên để số N mới sau khi xoá chia hết cho 3

Cho một số tự nhiên N, bằng cách giữ nguyên hoặc xoá đi một số chữ số liên tiếp của n (nhưng không xoá hết) ta nhận được một số mới, nếu số N được chia thành 2 phần thì số mới được ghép từ hai phần này và giữ nguyên thứ tự.
Yêu cầu:
Hãy xác định tất cả các cách xoá như trên để số N mới sau khi xoá chia hết cho 3. Lưu ý là hai vị trí khác nhau sẽ tạo ra hai cách xoá khác nhau. Số N giữ nguyên được coi là một cách xoá
input    output
1005        4
2009        3
c++ nha mn