Suppose you are given two strings a and b. You can apply the following operation any number of times: choose any contiguous substring of a or b, and sort the characters in it in non-descending order. Let f(a, b) the minimum number of operations you have to apply in order to make them equal (or f(a, b) = 1337 if it is impossible to make a and b equal using these operations).

For example: 

  * f(ab, ab) = 0; 
  * f(ba, ab) = 1 (in one operation, we can sort the whole first string); 
  * f(ebcda, ecdba) = 1 (in one operation, we can sort the substring of the second string starting from the 2-nd character and ending with the 4-th character); 
  * f(a, b) = 1337. 



You are given n strings s_1, s_2, ..., s_k having equal length. Calculate ∑ _{i = 1}^{n} ∑_{j = i + 1}^{n} f(s_i, s_j).

Input

The first line contains one integer n (1 ≤ n ≤ 2 ⋅ 10^5) — the number of strings.

Then n lines follow, each line contains one of the strings s_i, consisting of lowercase Latin letters. |s_1| = |s_2| = … = |s_n|, and n ⋅ |s_1| ≤ 2 ⋅ 10^5. All these strings are pairwise distinct.

Output

Print one integer: ∑ _{i = 1}^{n} ∑_{j = i + 1}^{n} f(s_i, s_j).

Examples

Input


4
zzz
bac
abc
acb


Output


4015


Input


2
a
b


Output


1337
#include <bits/stdc++.h>
const int B=200;
typedef long long ll;
using namespace std;
int T,n,m,l;
map<string,vector<string> >V;
map<string,bool>vis;
string s,t;
int main(){
	ios_base::sync_with_stdio(0), cin.tie(0);
	cin>>n;
	for(int i=1;i<=n;i++){
		cin>>s;t=s;
		sort(t.begin(),t.end());
		V[t].push_back(s);
	}
	l=s.size();
	ll ans=0,sum=0;
	for(auto it:V){
		auto &v=it.second;
		m=v.size(),ans+=sum*m*1337,sum+=m;
		if(m<=200*l){
			for(int i=0;i<m;i++) for(int j=i+1;j<m;j++){
				int L=0,R=l-1;
				while(v[i][L]==v[j][L]&&L<=R) L++;
				while(v[i][R]==v[j][R]&&L<=R) R--;
				int f1=1,f2=1;
				for(int k=L;k<R;k++){
					f1&=(v[i][k]<=v[i][k+1]);
					f2&=(v[j][k]<=v[j][k+1]);
				}
				if(f1||f2) ans++;
				else ans+=2;
			}
			continue;
		}
		ll nw=m*(m-1ll);
		vis.clear();
		for(auto &s:v) vis[s]=true;
		for(auto &s:v){
			for(int i=0;i<l;i++) for(int j=i+2;j<=l;j++){
				t=s,sort(t.begin()+i,t.begin()+j);
				if(t[i]!=s[i]&&t[j-1]!=s[j-1]&&vis.count(t)) nw--;
			}
		}
		ans+=nw;
	}
	cout<<ans<<"\n";
}
