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.

Background

luogu P1435

2022-2023春季学期初一信息竞赛组期中考第二题

Description

小A很喜欢回文串，他想将自己见到的一个字符串s变成回文串，但他只能向这个串里添加字母。给定字符串s，问小A至少需要添加多少个字母才能让它变成回文串。

注：此问题区分大小写

Format

Input

输入只有一行为一个字符串。

Output

一个正整数表示最少要添加的字符数量。

Samples

Ab3bd

2

Limitation

对$30\%$的数据，$length(s)≤100$；

对$100\%$的数据，$length(s)≤5*10^3$。