You have been tasked with hosting the annual Christmas Carol Competition at your school. This year, you've received hundreds of submissions and being too lazy to read through all of them, you decide to write a program that will judge the submitted songs for you.
Your program will give each song a score based on how well it rhymes. For any pair of
two lines, that pair's rhyme score is equal to the longest common suffix the last words of
each line share. For example, the rhyme score for the two lines
That light and
bright would be 4, as the longest suffix that
bright share is
ight, which is
four letters long.
The score for an entire song is equal to the sum of the rhyme scores for all possible pairs of lines in the poem. Given a song, find it's score.
The first line of the input provides the number of test cases, . test cases follow. Each test case begins with an integer , the number of lines in the song. lines follow, each containing a line of the song. Each line will contain only lowercase or uppercase letters and your program should NOT be case-sensitive.
For each test case, output one integer, the song's score.
2 4 Is this the real life Is this just fantasy Caught in a landslide No escape from reality 4 Yo yo it's Kayne West I'm the Kanye best If you put me to the Kayne test I'll show you I'm no Kanye jest