Задача C. Правдивая летопись

Автор:И. Туфанов   Ограничение времени:2 сек
Входной файл:input.txt   Ограничение памяти:64 Мб
Выходной файл:output.txt  

Условие

"...И узрели они войско вражье хазарское. И было хазарам несметное число." — Тут летописец задумался. Он знал, что число воинов было равно N. Однако, это число могло делиться на три, а могло (что еще хуже) содержать цифру три в десятичной записи! Число три счастливое, а это никак не согласуется с образом врага!

Поэтому летописец решил написать вместо числа N другое число M, которое не делится на три и не содержит в десятичной записи цифру три. Разумеется, число M не может быть меньше N (летописец не преуменьшает количество воинов). С другой стороны, число M должно как можно меньше отличаться по величине от N, иначе летописца могут обвинить в некомпетентности. Помогите летописцу найти нужное M.

Формат входного файла

Во входном файле содержится натуральное число N, записанное без лидирующих нулей.

Формат выходного файла

Выходной файл должен содержать минимальное подходящее число M (M ≥ N), записанное без лидирующих нулей.

Ограничения

Десятичная запись числа N содержит от 1 до 10000 цифр.

Примеры тестов

Входной файл (input.txt) Выходной файл (output.txt)
1
1
1
2
3
4
3
12
14

0.063s 0.007s 13