Akie 想去地球旅游一次，并希望报销她的旅行费用。然而，据说她只有在解决了以下问题后才能获得报销。你能帮她免费旅行吗？

一个字符串被称为“免费字符串”（free string），当且仅当它仅由 W 和 B 组成，且没有两个相邻的字符相同。

现在，给你一个长度为 $n$ 且仅由 W 和 B 组成的字符串 $s$。你最多可以进行一次操作：选择一个子串 $s_{l,r}$ ($1 \le l \le r \le n$)，并将其替换为相同长度的“免费字符串”。

要使整个字符串变成“免费字符串”，你需要选择的子串的最小长度是多少？如果不需要任何操作，输出 0。

输入格式

唯一的一行包含一个长度为 $n$ 且仅由 W 和 B 组成的字符串。保证 $1 \le n \le 2 \times 10^5$。

输出格式

一个整数，表示答案。

样例

输入样例 1

WBBBBBW

输出样例 1

3

输入样例 2

BBWW

输出样例 2

2

说明

在第一个样例中，你可以选择子串 $s_{3,5}$ 并将其替换为 WBW。

在第二个样例中，你可以选择子串 $s_{2,3}$ 并将其替换为 WB。