問題文

N 個の文字列 S_1, S_2, \dots, S_N が与えられます。空でない文字列 T であって、以下の条件を満たすものの個数を求めてください。

• 文字列 S_1, S_2, \dots, S_N のうち、T を (連続する) 部分文字列として含むものはちょうど 1 個である。

制約

• 1 \le N \le 10^5
• 1 \le |S_i| \le 10^6\ (1 \le i \le N)
• \left(\sum_{i=1}^{N} |S_i|\right) \le 10^6
• S_i\ (1 \le i \le N) は英小文字からなる文字列

入力例 1

2
abc
ca

出力例 1

5

T = {}a の場合を考えると、S_1 = {}abc と S_2 = {}ca の 2 個が a を部分文字列として含むので、条件を満たしません。

T = {}ab の場合を考えると、S_1 = {}abc のみが ab を部分文字列として含むので、条件を満たします。

T = {}d の場合を考えると、S_1 = {}abc も S_2 = {}ca も d を部分文字列として含まないので、条件を満たしません。

条件を満たす文字列は T = {}b, ab, bc, ca, abc の 5 個です。

入力例 2

2
aab
aab

出力例 2

0

T = {}ab の場合を考えると、S_1 = {}aab と S_2 = {}aab の 2 個が ab を部分文字列として含むので、条件を満たしません。

条件を満たす文字列はありません。

入力例 3

1
aba

出力例 3

5

条件を満たす文字列は T = {}a, b, ab, ba, aba の 5 個です。

入力例 4

3
tokyoinstituteoftechnology
tokyomedicalanddentaluniversity
instituteofsciencetokyo

出力例 4

905