SP2743 PRETILE - Prefix Tiling

You are given a string S with N (1 ≤ N ≤ 100,000) characters from 'A' to 'Z', inclusive. For an integer L between 1 and N, inclusive, we define match (L) as the length of the longest prefix of S that can be tiled by the length-L prefix of S; more specifically, match (L) is the smallest 0-based index k such that S \[k\] ≠ S \[k mod L\], or N if no such k exists. For example, when S = "ABCAB", match (1) = 1, match (3) = 5, and match (4) = 4. Compute the sum match (1) + match (2) + ... + match (N).

The first line contains the integer T (1 ≤ T ≤ 10), the number of tests. For each test, there is a single line containing the string S.

For each test case, print a single line containing one integer: the value of match (1) + match (2) + ... + match (N).