题目描述

有一个字符串集合$S$，定义一个字符串为“好”的，当且仅当它可以被分成非空的两段，其中每一段都是字符串集合$S$中某个字符串的前缀。 比如对于字符串集合{“abc”,“bca”}，字符串“abb”、“abab”是“好”的（“abb”=“ab”+“b”, “abab”=“ab” +“ab”），而字符串“bc”不是“好”的。 求一共有多少个不同的“好”的字符串。

输入

第一行一个整数$n$，表示字符串集合中字符串的个数 接下来每行一个字符串。

输出

一个整数，表示有多少不同的“好”的字符串。

输入样例

2
ab
ac

输出样例

9

提示

【数据规模】 对于20%的数据，$1≤n≤200$。 对于50%的数据，$1≤n≤2000$。 对于100%的数据，$1≤n≤10000$，每个字符串非空且长度不超过$30$，均为小写字母组成。

评测数据说明

本题使用按题意独立构造、以独立程序核对的训练数据及公开样例，共6个测试点，非原站或官方原始数据。总分100分。