翻译：

给定一个字符串 $s$ ，求最小的正整数 $k$ 使得 $s$ 可以写成 $s_1s_2\dots s_k$ ，其中 $s_1,s_2,\dots,s_k$ 均为回文串

Input:

4
abacdc
ababa
ababbacababbad
abcd

Output:

2
1
5
4

@Maxmilite