定义无限 Fibonacci 单词序列 $S_0, S_1, S_2, S_3 \dots$ 如下：

• $S_0 = \text{b}$
• $S_1 = \text{a}$
• $S_i = S_{i-1}S_{i-2}$，其中 $i \ge 2$

该序列的前几项如下：

• $S_0 = \text{b}$
• $S_1 = \text{a}$
• $S_2 = \text{ab}$
• $S_3 = \text{aba}$
• $S_4 = \text{abaab}$
• $S_5 = \text{abaababa}$
• $S_6 = \text{abaababaabaab}$

容易发现，除了 $S_0$ 外，每个单词都是下一个单词的前缀。因此，我们可以定义一个无限 Fibonacci 单词 $S$，其第 $i$ 个字符即为该无限 Fibonacci 单词序列（排除 $S_0$）中长度至少为 $i$ 的单词的第 $i$ 个字符。

给定一个仅由字符 ‘a’ 和 ‘b’ 组成的单词 $t$。你的任务是找到一个最短的单词 $s$，使得 $s$ 是 $S$ 的一个子串，且 $t$ 是 $s$ 的一个子序列，并输出 $s$ 的长度。

输入包含一行，为一个单词 $t$，仅由字母 ‘a’ 和 ‘b’ 组成。$t$ 的长度至少为 1，至多为 $150,000$。

输出一个整数，表示所求单词 $s$ 的最小可能长度。

样例

输入格式 1

aabbaab

输出格式 1

8

说明

$S$ 中不存在长度为 7 或更短的子串包含 $t$ 作为子序列。然而，$S$ 包含子串 aababaab，从中删去第四个字符即可得到 $t$。因此，$s$ 的最小长度为 8。