Yalda 想要在 Bahar 生日时送给她一份精美的礼物。她在纸上画出了一条由 $n$ 颗不同颜色的珠子组成的项链草图。这条项链用一个长度为 $n$ 的字符串表示，字符串由小写英文字母组成，每个字母代表珠子的一种颜色。26 个英文字母分别代表 26 种不同的颜色。Yalda 拥有无限多各种颜色的珠子，她打算用这些珠子制作项链。然而，由于 Bahar 的生日临近，她的时间很紧，想要以最少的步骤完成项链的制作。Yalda 最初有两条空项链。其中一条将作为最终的礼物，另一条是她在制作过程中使用的缓冲项链。在每一步中，她可以执行以下操作之一：

• 在缓冲项链的任意位置添加一颗所需颜色的珠子，
• 从缓冲项链的任意位置移除一颗珠子，
• 将缓冲项链中的一颗珠子替换为所需颜色的珠子，或者
• 将缓冲项链中的珠子序列追加到主项链的末尾。添加的字符串将与缓冲项链完全相同。但是，在复制过程中，缓冲项链中珠子的顺序会被反转（例如，如果执行此操作前主项链为 pq，缓冲项链为 abc，则操作后主项链变为 pqabc，缓冲项链变为 cba）。

如果能告诉她制作该项链所需的最少步骤，Yalda 将不胜感激。

输入格式

输入仅包含一行，为一个非空字符串，由小写英文字母组成，长度不超过 300。该字符串表示所需项链的草图。

输出格式

输出仅包含一行，为一个整数，表示制作该项链所需的最少步骤数。

样例

样例输入 1

abaadbcceaaefc

样例输出 1

12

样例输入 2

abaddbeageabdkpkdbeqg

样例输出 2

16