问题陈述
你被给予 N 字符串 S_1,\ldots,S_N.
查找整数对的数量 (i,j) 这样:
- 1 \leq i,j \leq N,和
- S_i 是以下序列的子序列 S_j.
什么是子序列? 字符串的
A 子序列 是通过删除零个或多个位置的字符并连接剩余字符而不改变其顺序而获得的字符串。 例如,a, pe,和 apple 是子序列 apple,但是 ea 和 hoge 不是。
约束
- 1 \leq N \leq 10^5
- N 是一个整数。
- S_i 是长度介于 1 和 5,包含在内,由小写英文字母组成。
输入
输入由标准输入按以下格式给出:
N S_1 \vdots S_N
输出
打印答案。
示例输入 1
3 ps past post
示例输出 1
5
九对整数中 (i,j) 这样 1 \leq i,j \leq N,以下五个满足条件 S_i 是以下序列的子序列 S_j.
- (i,j)=(1,1)
- (i,j)=(1,2)
- (i,j)=(1,3)
- (i,j)=(2,2)
- (i,j)=(3,3)
示例输入 2
5 a aa aaa aaaa aaaaa
示例输出 2
15
示例输入 3
2 hoge hoge
示例输出 3
4