この問題はABC307-B(racecar)の強化版です

問題文

英小文字からなるNN個の文字列S1,S2,,SNS_1,S_2,\cdots,S_Nが与えられる。
11以上NN以下の相異なる整数i,ji,jであってSiS_i,SjS_jをこの順番で繋げたものが回文であるものの個数を答えなさい。

制約

  • 2N1052 \leq N \leq 10^5
  • 1Si1051 \leq |S_i| \leq 10^5
  • Si2×105\sum |S_i| \leq 2 \times 10^5
  • NNは整数である
  • SiS_iは英小文字のみからなる文字列

入力

入力は以下の形式で標準入力から与えられます

NN
S1S_1
\vdots
SNS_N

出力

もし回文を作れないのならば 00 を出力してください

サンプル

入力1
4
go
run
dog
nurses
出力1
2
入力2
2
pon
juice
出力2
0

提出


Go (1.21)