Для передачи сообщений по каналу связи используются последовательности из цифр 0, 1, 2, 3 и 4. Так как при передаче сообщений возможны помехи, было решено отправлять последовательности длиной, кратной 3, где цифры объединены в блоки по 3 цифры, причём в каждом блоке сумма цифр равна 8 (тогда, если сумма цифр не равна 8, значит, в блоке были помехи и его надо переслать).
Пример такой последовательности: 440 431 224
Какой длины должны быть последовательности, чтобы можно было передать как минимум 10^11 различных последовательностей именно этой длины?
Пример: если передаются 0 и 1 блоками по две цифры, где каждый блок имеет сумму 1, то последовательностей длины 4 будет 4: 10 10, 10 01, 01 10, 01 01.
Формат ввода ответа
В ответе укажите одно целое число.