import java.util.Scanner;

public class StringSimilarity { public static void main(String[] args) { Scanner scanner = new Scanner(System.in); int t = scanner.nextInt(); // Number of test cases

    while (t-- > 0) {
        String s = scanner.next(); // Input string
        int n = s.length();
        int[] z = zFunction(s);
        long sum = 0;

        for (int i = 0; i < n; i++) {
            sum += z[i];
        }

        System.out.println(sum); // Output sum of similarities
    }

    scanner.close();
}

// Function to compute Z array for a given string
private static int[] zFunction(String s) {
    int n = s.length();
    int[] z = new int[n];
    z[0] = n;
    int l = 0, r = 0;

    for (int i = 1; i < n; i++) {
        if (i <= r) {
            z[i] = Math.min(r - i + 1, z[i - l]);
        }

        while (i + z[i] < n && s.charAt(z[i]) == s.charAt(i + z[i])) {
            z[i]++;
        }

        if (i + z[i] - 1 > r) {
            l = i;
            r = i + z[i] - 1;
        }
    }

Read the number of test cases and input strings. For each string, compute its Z array using the Z algorithm. Sum up the values in the Z array to get the similarity. Output the similarity for each string. Repeat for each test case.

    return z;
}

}