E. Exotic Algorithm (Easy Version)
time limit per test
1.5 seconds
memory limit per test
1024 megabytes
input
standard input
output
standard output

This is the easy version of the problem. The only difference between the two versions is the constraint on $$$|s|$$$ .

Navarro is (or was? I'm really not sure) a prominent student at the Institute of Making Ethanol, commonly known around the block as IME. He loves playing around with strings (of characters, not related to ropes) and so he also enjoys applying random algorithms to them. On one fine afternoon, he devised a simple algorithm to create a graph from a string with the following construction: two indices $$$i$$$ and $$$j$$$ are connected only if the substring $$$[i, j]$$$ is a palindrome. Seems simple right?

From the graph that's created, Navarro wants to find out the amount of connected components.

Input

The input consists of a single string $$$s$$$, $$$(1 \leq |s| \leq 10^4)$$$, containing only lowercase Latin letters.

Output

Output a single integer — the amount of connected components in the graph that's generated.

Examples
Input
abcacba
Output
4
Input
navarrolikestacocat
Output
14
Note

We can see that the resulting graph will have the following edges:

1-7

2-6

3-5

Thus, there will be 4 connected components.