题目描述

小due想要背由 ‘a’’b’’c’’d’’e’’f’’g’ 中字母组成的单词。但是小due 最近误服了药物,只能一次记住两个字母。如果要记得更长,就需要将两串字母拼接起来。且能拼接的两个字母串需要满足前串字母的末尾字母和后串字母的开头字母相同。
例如小 due 已经记住了 ab 和 ba,那么他可以把这两串字母拼起来,变成 aba(注意拼的过程中会删去那个相同的字母),然后再和 ab 拼成 abab。定义这样的两个字母组成的字母串为基字母串。
那么小due至少需要多少个不同的基字母串,才能使他记住单词s?


输入格式

两行。第一行为单词s的长度n,$2 \leq n \leq 10^6$。
第二行为一个字符串,即单词s。


输出格式

基字母串的个数


样例数据

输入

4
abab

输出

2

备注

样例解释:
基字母串为ab和ba


操作

评测记录

优秀代码

信息

时间限制: 1s
内存限制: 128MB
评测模式: Normal

题解