VPALIN - Finding Palindromes

no tags 

A word is called a palindrome if we read from right to left is as same as we read from left to right. For example, "dad", "eye" and "racecar" are all palindromes, but "odd", "see" and "orange" are not palindromes.

Given n palindromes, you can generate n × n pairs of them and concatenate the pairs into single words. The task is to count how many of the so generated words are palindromes.

Input

The first line of input file contains the number of strings n. The following n lines describe each string: The i+1-th line contains the length of the i-th string li, then a single space and a string of li small letters of English alphabet. You can assume that the total length of all strings will not exceed 2,000,000. Two strings in different line may be the same.

Output

Print out only one integer, the number of palindromes.

Example

Input:
3
1 a
2 bb
2 aa


Output:
5

Explanation

The 5 palindromes are: aa aaa aaa bbbb aaaa


hide comments
parthkohli: 2019-08-21 20:42:35

@Karim Ihab El Sheikh: ab is not a palindrome

shikhar jindal: 2016-07-28 07:24:00

what is the limit on n?

Shikhar: 2016-01-27 17:51:46

The test cases provided in comments are wrong because the question states that the n strings provided are all palindromes

sesy: 2015-09-08 22:32:11

how and where to use KMP ?

badry atef: 2015-06-27 18:08:08

my output for this case is 1 but i get TLE :(

Karim Ihab El Sheikh: 2015-06-21 01:24:30

Lol, even though I get accepted my code doesn't handle a case like this
2
5 abbaa
7 bbaabba

Answer should be 1 but I print 0

Karim Ihab El Sheikh: 2015-06-19 00:31:47

For WA, try this test case
5
12 abaabaabaaba
9 abaabaaba
3 aba
2 ab
1 b

Answer = 11

Ryuzaki: 2014-08-13 05:08:25

very strict time limit :(
took me 43 submissions to get AC using trie.

Last edit: 2014-08-13 05:14:47
Nguyen Tien Trung Kien: 2014-02-02 15:11:38

when I used trie, firstly, the trie size is exceeded memory limit, after I change an array int[30] by map<char, int>, the excution time is 32s, when I used map<string, int> the execution time is 7,2s.

Srijan Khare: 2013-12-28 16:16:14

strict time limit... but trie did it for me :) ...nice problem


Added by:Phenomenal
Date:2009-02-15
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ERL JS-RHINO NODEJS PERL6 VB.NET
Resource:POI 2006