Вася считает, что счастливые билеты — это билеты, номера которых делятся на 3 без остатка. Ему удалось собрать достаточно большую коллекцию таких билетов, но однажды его младший брат Леонид обиделся на него и решил уничтожить всю коллекцию. Сначала он разорвал каждый билет ровно на два кусочка, но этого ему показалось мало, поэтому Леонид еще и выкинул часть кусочков. Увидев это, Вася пришел в ужас, но все-таки попытался восстановить коллекцию. Он выбрал несколько пар кусочков, и попарно склеил их так, чтобы каждая пара образовывала счастливый билет. Оставшиеся кусочки Вася, скрепя сердце, выкинул. Таким образом, после склейки 2t кусочков у него получилось t билетов, каждый из которых — счастливый.
Когда Леонид разрывал билет на два кусочка, на одном оказывались первые несколько цифр его номера, а на втором — вся оставшаяся часть.
Каждую пару кусочков Вася может склеить так, как ему захочется, лишь бы получался счастливый билет. Например, кусочки 123 и 99 можно склеить ровно двумя способами: 12399 и 99123.
Какое наибольшее число билетов могло получиться у Вася после этого?