408436: GYM103118 F Birthday Cake

Moca's birthday is coming up, and her friend Ran is going to the Yamabuki bakery to order a birthday cake for her.

Yamabuki bakery provides $$$n$$$ kinds of cake. Since Ran knows that Moca is the Yamabuki Bakery's $$$1$$$-st fan and can eat a lot of food, she intends to order two cakes and put them together into a big cake. The cake made by Yamabuki bakery can be formed by a string consisting of lowercase Latin letters, which describes the toppings on the cake, such as strawberries and chocolate. Putting two cakes together is the concatenation of two corresponding strings. For example, the result of putting cake ab and cake cabc together is a big cake abcabc.

To make it easier to share the cake, Ran will choose two cakes and put them together into a big cake which can be divided in half into two identical pieces. For example, cake abcabc will be divided in half into two cakes abc, but cake abbc will be divided in half into two different cakes ab and bc. Notice that Ran can not reverse the cake, which means that cake abba will be divided into two different cakes ab and ba.

Can you help Ran figure out how many different pairs of cakes meet the above condition?

The first line contains one integer $$$n$$$ $$$(1 \le n \le 4 \cdot 10^5)$$$ – the number of cakes.

The next $$$n$$$ lines describe all the cakes, where the $$$i$$$-th line contains one string $$$s_i$$$ $$$(1 \le |s_i| \le 4 \cdot 10^5)$$$ consisting of lowercase Latin letters.

It is guaranteed that the sum of lengths of cakes does not exceed $$$4 \cdot 10^5$$$.

Print one integer – the number of pairs of cakes meet the above condition.

3
ab
ab
cabc

3

3
abc
a
cabc

0

4
hhh
hhh
hhh
hhh

6