A string is called a repeat-once string if we can obtain it by concatenating two copies of the same string. For example, xxyxxy and xx are repeat-once strings, while xxx and xyyx are not. Given a string, calculate the number of non-empty subsequences of the string such that they are repeat-once strings. For example, given the string xxx it has three subsequences that are repeat-once strings, each of them is xx (the first and second x from xxx, the second and third x, and the first and third x).
The first line of the input is an integer T, which is the number of test cases. The next T lines contain test cases, each of which contains a string. You can assume that 1 ≤ T ≤ 200 and that each string in the test case is of length at most 200, and consists only of lower-case letters (a−z).
For each test case, list the number of repeat-once subsequences on a separate line. The output should therefore have T different lines.
For the first test case, there is only one repeat-once subsequence, namely aa. For the second, there are 3 identical repeat-once subsequences xx. For the last test case, there are the following repeat-once subsequences: aa (3), bb (3), ab (5), and ba(1)
For the constraints given above, your program should run in 3 seconds. You must submit source code for a program written in C/C++/Java on the Electronic Assignment System. Some test cases will be provided on the course website. You can verify if your program works on the test cases before submitting.
There will be a programmer-on-duty, Tejas Puranik, available to help you with the assignment on Wednesdays 6pm to 9pm in H841.