#P18864. [HONI 2011/2012 #5] RAZBIBRIGA

[HONI 2011/2012 #5] RAZBIBRIGA

题目描述

从给定词表中挑出四个互不相同的单词,分别作为正方形的上、下、左、右边。横边上的单词从左到右读,竖边上的单词从上到下读。每个角同时属于一横一竖两条边,这两个单词在该角的字母必须相同。

求能组成多少个不同的正方形。只要有一个位置的字母不同,就视为两个不同的正方形。

输入格式

第一行一个整数 NN,满足 4≤N≤1000004\le N\le100000。

接下来 NN 行,每行一个由大写英文字母组成的单词。所有单词互不相同,长度相同且不超过 1010。

输出格式

输出能够组成的不同正方形数。答案保证能用有符号 64 位整数表示。

样例

样例 1

输入

4
NIVA
HLAD
HSIN
DEDA

输出

2

样例 2

输入

6
BAKA
BARA
BALC
CALC
ARHC
BLIC

输出

8