Polycarp has a poor memory. Each day he can remember no more than 3 of different letters.

Polycarp wants to write a non-empty string of s consisting of lowercase Latin letters, taking minimum number of days. In how many days will he be able to do it?

Polycarp initially has an empty string and can only add characters to the end of that string.

For example, if Polycarp wants to write the string lollipops, he will do it in 2 days:

• on the first day Polycarp will memorize the letters l, o, i and write lolli;
• On the second day Polycarp will remember the letters p, o, s, add pops to the resulting line and get the line lollipops.

If Polycarp wants to write the string stringology, he will do it in 4 days:

• in the first day will be written part str;
• on day two will be written part ing;
• on the third day, part of olog will be written;
• on the fourth day, part of y will be written.

For a given string s, print the minimum number of days it will take Polycarp to write it.

Polycarp 的記憶力很差。 每天他能記住的不同字母不超過 3 個。

Polycarp 想要寫一個由小寫拉丁字母組成的非空字符串 s，需要最少的天數。 幾天后他能做到？

Polycarp 最初有一個空字符串，並且只能在該字符串的末尾添加字符。

比如Polycarp想寫字符串 lollipops，他會在2天內完成：

第一天，Polycarp 會記住字母 l、o、i 並寫出 lolli；
第二天，Polycarp 將記住字母 p、o、s，將 pops 添加到結果行中並得到 lollipops。

如果 Polycarp 想寫 stringology，他會在 4 天內完成：

第一天將寫 str；
第二天將寫 ing；
第三天將寫 olog；
第四天，y 被寫入。

對於給定的字符串 s，打印 Polycarp 編寫它所需的最少天數。