5815 - 集训: 删除字符

通过次数

84

提交次数

181

Time Limit : 1 秒
Memory Limit : 128 MB

告诉你一个全是小写字母构成的字符串,里面有若干个tzyz,但是里面也有可能被其他字符隔开了,现在请问你至少删除几个才能有连续的四个字符abcd,如果无法做到则输出-1

Input

多组数据 每组数据包含一个字符串 1 <= n <= 100000

Output

输出一个整数表示最少需要删除的字符数,若不存在则输出"-1"。

Examples

Input

abcd
dfer
abcefd

Output

0
-1
2

Hint

最多100组