ruaaaa

题目描述

给出一个小写字母组成的字符串 $s$，求它的最小循环节长度。

循环节：串 $s$ 的循环节 $t$ 满足，串 $s$ 仅由 $t$ 循环拼接若干次得到。例如 abcabcabc 的一个循环节是 abc。

最小循环节：串 $s$ 的最小循环节 $t'$ 满足，对串 $s$ 的任何一个循环节 $t$，都有 $t'$ 是 $t$ 的循环节。

输入

第一个数为数据组数 $T(1\leq T\leq 20)$。

接下来 $T$ 行，每行一个字符串（仅由小写字母构成），长度不超过 $500$。

输出

对于每组数据，输出一行，一个整数，表示该串的最小循环节的长度。

输入样例

2
aaaaaa
abcd

输出样例

1
4