G. Copy and Paste
time limit per test
1 s
memory limit per test
512 megabytes
input
standard input
output
standard output

Given a lowercase string $$$s$$$, you have an initially empty clipboard and input box. You need to generate $$$s$$$ using as few operations as possible. Find the minimum number of operations required.

Each operation can be one of the following three types:

1. Insert a lowercase letter at the end of the input box.

2. Clear the clipboard and copy all the text in the input box to the clipboard.

3. Insert all the content in the clipboard at the end of the input box.

Input

One line containing a lowercase string $$$s$$$. The length of the string is between $$$1$$$ and $$$10^5$$$.

Output

One line containing an integer representing the minimum number of operations.

Examples
Input
aabaab
Output
5
Input
aaaaaabaaa
Output
7
Note

In the first testcase, we can generate "aabaab" within the following steps:

Step IDOperationClipboardInput box
0-
1Insert aa
2Insert aaa
3Insert baab
4Copyaabaab
5Pasteaabaabaab

 

And in the second testcase, we can generate "aaaaaabaaa" within the following steps:

Step IDOperationClipboardInput box
0-
1Insert aa
2Insert aaa
3Insert aaaa
4Copyaaaaaa
5Pasteaaaaaaaaa
6Insert baaaaaab
7Pasteaaaaaaaaabaaa