Число делится на 3, если сумма его цифр делится на 3.
Сумма цифр числа *123 равна * + 1 + 2 + 3 = * + 6.
Чтобы число делилось на 3, * может быть 0, 3, 6, 9. Чтобы число не делилось на 9, * не может быть 3 или 9 (так как *+6 будет делиться на 9). Наименьшая подходящая цифра для * - 0.