You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

假设字符串 $S_0=\tt b$，$S_1=\tt a$，且 $S_i=S_{i-1}S_{i-2}$（这里是拼接运算）。不难发现 $S_{998244353}=\tt abaababaabaab\dots$。

巡告诉你一个字符串 $T$，你需要告诉巡最小的 $len$ 满足存在一个 $1\leq i\leq 10^{18}$ 满足 $T$ 是 $S_{998244353}[i,i+len-1]$ 的子序列。

输入格式

一行一个字符串表示 $T$。

输出格式

一行一个正整数表示答案。

样例 #1

【样例输入】

aabbaab

【样例输出】

8

样例 #2

见下发 $\textit{fib2.in/ans}$。

该测试点满足测试点 $1$ 的性质。

数据范围

对所有数据保证 $1\leq n\leq 10^5$，$T$ 只包含 $\tt ab$ 两种字符。