SP5301 QUERYSTR - Query Problem

McFn interesed in string problem recently.He found a interesing function and he felt he could use this function to invent a new match algorithm. For a string S \[1 ... n\] and i ¡Ê \[1, n\], define F (i) is the length of the longest common suffix of S and S \[1 ... i\]. For example, for the string S \[1 ... 11\] = zaaxbaacbaa, then F (1) = 0, F (2) = 1, F (3) = 2 (note that S \[1 ... 3\] = zaa), F (4) = 0, ... ... F (10) = 1, F (11) = 11; For the string S \[1 ... n\], i ¡Ê \[1, n\], S \[i ... n\] is its suffix;

The first line is a integer T.the number of test cases for each test case The first line is a string S, composed of only lowercase letters, len (s) is the length of s, 1

For each x the output F (x);