Нужно на C++

Дано число. В этом числе необходимо изменить одну цифру таким образом,чтобы новое число делилось на 3 и было бы максимально возможным. В исходном числе нужно обязательно изменить одну цифру,даже если исходное число уже делилось на 3.
Программа получает на вход одно длинное натуральное число.Длина числа может достигать 100 цифр.
Программа должна вывести другое натуральное число,удовлетворяющее условиям:
1)Новое число должно отличаться от данного ровно одной цифрой.
2)Новое число должно делиться на 3.
3)Новое число должно быть максимально возможным из всех таких чисел.

А что для этого нужно?какие циклы

любые, но лучше for

Спасибо

Кстати,забыл спросить как сделать левую цифру больше

Прежде всего нужно определить остаток от деления исходно числа на 3. для этого, т.к. у вас будет строка вам нужно посчитать сумму отдельных символов строки и взять остаток суммы от деления на 3. Если этот остаток равен  :А) 0, то нужно увеличить любую цифру числа на 3 или 6 или 9 и нужно изменить 1 цифру так, что бы остаток от деления на 3 не изменился. Б) 1, то одну цифру числа нужно увеличить на 2 или 5В) 3, то на 1 или 4 или 7Для того чтобы число было макс. большим нужно брать максимально левую цифру для увеличения.Ну, как-то так