Андрей очень любит двоичные последовательности — последовательности, состоящие только из цифр 0 и 1. В особенности он любит последовательности, в которых цифры чередуются. Недавно Андрей придумал новое обозначение: sn — это двоичная последовательность длины n, в которой цифры чередуются, а первая цифра равна 0. Например, s6=010101, s3=010, а s1=0.

Сегодня Андрею на глаза попалась двоичная последовательность t. Ему стало интересно, какова минимальная длина последовательности sm, для которой строка t является ее подпоследовательностью. Напомним, что b называется подпоследовательностью a, если из a можно вычеркнуть некоторые цифры, чтобы получилась последовательность b. Иными словами, Андрей хочет найти минимальное число m, для которого верно, что можно вычеркнуть из последовательности sm некоторые цифры, чтобы получилась последовательность Андрею справиться с этой непростой задачей.