Aloknath is fond of shlokas.His bitiya pooja gave him an shloka of â€˜Nâ€™ characters. Babuji calls a shloka SANSKARI (length>1) if it can be cut from the middle yielding exactly 2 identical shloka.

Now pooja gave babuji a task to find out the total number of SANSKARI shlokas starting from the first character of the given shloka.

Can you do this task for babuji?

Input : t no of test cases and t lines follow each containing a shloka. A shloka is a alphanumeric string of characters.

Output : t lines.The i th line containing answer for the i th case.

Constraints : 0 < t < 10 0 < length of string < 10^5.