A lab stores short symbol sequences that are supposed to read the same forwards and backwards. A transmission glitch dropped some symbols, leaving the sequence incomplete.

To repair it, you may insert symbols anywhere in the string. You can insert any characters as many times as needed. Determine the minimum number of insertions required to make the string a palindrome.

A palindrome is a string that reads the same from left to right and right to left.

---

Example 1

Input

s = "ab"

Output

1

Explanation

One possible repair is inserting 'a' at the end to form "aba". Another possible repair is inserting 'b' at the front to form "bab". Both require only one insertion.

---

Example 2

Input

s = "mbadm"

Output

2

Explanation

The string can be transformed into "mbdadbm" by inserting two characters. Therefore, the minimum number of insertions required is 2.

---

Input Format

The input contains a single string s.

---

Output Format

Return a single integer representing the minimum number of character insertions required to make s a palindrome.

---

Constraints

• 0 ≤ len(s) ≤ 2000
• s consists only of lowercase English letters.

---

Sample Case 0

Sample Input 0

ab

Sample Output 0

1

---

Function Signature

int minInsertions(string s)

Return

Return an integer representing the minimum number of insertions required to make the given string a palindrome.