题目描述

给定 $n$ 个字符串

保证它们互不相同。请求出满足如下条件的三元组 $(i,j,k)$ 的个数：

• $1\le i,j,k\le n$，且 $i,j,k$ 互不相同；
• $s_i$ 是 $s_j$ 的子串，$s_j$ 是 $s_k$ 的子串；
• 不存在一个 $j'\notin\{i,j,k\}$，使得 $s_i$ 是 $s_{j'}$ 的子串且 $s_{j'}$ 是 $s_k$ 的子串。

输入格式

第一行，一个正整数 $n$。

接下来 $n$ 行，每行一个字符串 $s_i$。

输出格式

一行，一个非负整数，表示答案。

样例 1 输入

4
ababa
baka
abab
ab

样例 1 输出

1

样例 2 输入

5
bc
cbcb
cbca
cbc
c

样例 2 输出

3

数据范围与子任务

记

对于所有数据：

所有 $s_i$ 都是仅由小写字母组成的非空字符串。

特殊性质 A：保证所有 $s_i$ 均仅由 a、b 组成，且每个 $s_i$ 中恰有一个 b。

特殊性质 B：保证所有 $s_i$ 均仅由 a、b 组成。