Background

24年初赛模拟题9阅读程序T2

Description

一个字符串，如果从左到右读和从右到左读是完全一样的，比如"aba"，我们称其为回文串。现在给你一个字符串，可在任意位置添加字符，求最少添加几个字符，才能使其变成一个回文串。

Format

Input

任意给定的一个字符串，其长度不超过1000.

Output

能变成回文串所需添加的最少字符数。

Samples

ab3bd

2

abb

1

Limitation

1s, 1024KiB for each test case.