E. Pattern Search II
time limit per test
4 seconds
memory limit per test
1024 megabytes
input
standard input
output
standard output

Let's define an infinite sequence of Fibonacci words $$$S_0, S_1, S_2, S_3\ldots$$$ as follows:

  • $$$S_0 = \texttt{b}$$$
  • $$$S_1 = \texttt{a}$$$
  • $$$S_i = S_{i-1}S_{i-2}$$$ for $$$i \geq 2$$$

The first few words of this sequence look as follows:

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

It is easy to notice that each word (except for $$$S_0$$$) is a prefix of the next one. Therefore, we can also define an infinite Fibonacci word $$$S$$$, where the $$$i$$$-th character is the $$$i$$$-th character of these words in the infinite sequence of Fibonacci words (except for $$$S_0$$$) that have at least $$$i$$$ characters.

You are given a word $$$t$$$ consisting only of the characters 'a' and 'b'. Your task is to find the shortest possible word $$$s$$$ that is a substring of $$$S$$$ and contains $$$t$$$ as a subsequence, and output its length.

Input

The standard input contains a single line with one word $$$t$$$, consisting only of the letters 'a' and 'b'. $$$t$$$ will contain at least one and at most $$$150,000$$$ characters.

Output

The output should contain a single integer, indicating the minimum possible length of the described word $$$s$$$.

Example
Input
aabbaab
Output
8
Note

$$$S$$$ does not contain a substring of length $$$7$$$ or less that contains $$$t$$$ as a subsequence. However, it does contain the substring aababaab, from which we can remove the fourth character, thus obtaining $$$t$$$. Therefore, the sought length of $$$s$$$ is $$$8$$$.