Bajtocki Zakład Poligraficzny (BZP) 接到了一个大订单，生产条纹壁纸，这是室内设计本季的热门产品。每张壁纸由 $n$ 条等宽的彩色竖条组成。BZP 将负责设计和印刷这些壁纸。客户预先指定了壁纸上某些条纹的颜色。对于其余的条纹，BZP 拥有完全的自由度。

BZP 使用印刷模板来印刷壁纸上的连续条纹。模板对印刷的每条条纹都有指定的颜色，并且可以比整张壁纸短。如果模板由 $k$ 条条纹组成，它将被放置在所有 $n - k + 1$ 个可能的位置上，使其条纹与壁纸的条纹重叠，每次都印刷模板的所有条纹。这样，壁纸的一条条纹可能会被印刷多次。如果给定条纹被印刷了不同的颜色，其最终颜色将是这些颜色的混合。

BZP 的员工，无论他们对美学有什么感受，都希望设计出尽可能短的模板，以便能够印刷整张壁纸。他们必须记住，对于客户指定的条纹，他们必须使用纯色，不能混合其他颜色。换句话说，每次放置模板覆盖此类条纹时，模板上该条纹的颜色必须与客户指定的颜色完全一致。

Input Format

输入唯一一行包含一个由拉丁大写字母和星号 (*) 组成的字符串，表示期望的壁纸外观。不同的字母代表不同的条纹颜色，而星号表示客户未指定颜色的条纹。字符串的长度 $n$ 满足 $1 \le n \le 1\,000\,000$。

Output Format

你的程序应该输出一行，包含一个整数 $k$：允许印刷所需壁纸的模板的最小长度。

Examples

Input

A*B*B*A

Output

6