Hongcow's teacher heard that Hongcow had learned about the cyclic shift, and decided to set the following problem for him.

You are given a list of n strings s1, s2, ..., sn contained in the list A.

A list X of strings is called stable if the following condition holds.

First, a message is defined as a concatenation of some elements of the list X. You can use an arbitrary element as many times as you want, and you may concatenate these elements in any arbitrary order. Let SX denote the set of of all messages you can construct from the list. Of course, this set has infinite size if your list is nonempty.

Call a single message good if the following conditions hold: 

  * Suppose the message is the concatenation of k strings w1, w2, ..., wk, where each wi is an element of X. 
  * Consider the |w1| + |w2| + ... + |wk| cyclic shifts of the string. Let m be the number of these cyclic shifts of the string that are elements of SX. 
  * A message is good if and only if m is exactly equal to k. 



The list X is called stable if and only if every element of SX is good.

Let f(L) be 1 if L is a stable list, and 0 otherwise.

Find the sum of f(L) where L is a nonempty contiguous sublist of A (there are <image> contiguous sublists in total).

Input

The first line of input will contain a single integer n (1 ≤ n ≤ 30), denoting the number of strings in the list.

The next n lines will each contain a string si (<image>).

Output

Print a single integer, the number of nonempty contiguous sublists that are stable.

Examples

Input

4
a
ab
b
bba


Output

7


Input

5
hh
ee
ll
ll
oo


Output

0


Input

6
aab
ab
bba
b
ab
c


Output

13

Note

For the first sample, there are 10 sublists to consider. Sublists ["a", "ab", "b"], ["ab", "b", "bba"], and ["a", "ab", "b", "bba"] are not stable. The other seven sublists are stable.

For example, X = ["a", "ab", "b"] is not stable, since the message "ab" + "ab" = "abab" has four cyclic shifts ["abab", "baba", "abab", "baba"], which are all elements of SX.
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 35;
const int MAXS = 100005;
long long n, b1 = 31337, b2 = 1299721, p1 = 1000000007, p2 = 1000000011, sol;
string s[MAXN];
int len[MAXN], bio[MAXS];
long long h1[MAXN][MAXS], h2[MAXN][MAXS];
long long pot1[MAXS], pot2[MAXS];
vector<int> c[MAXN], v[MAXS];
long long sub(long long a, long long b, long long mod) {
  if (a - b < 0) return a - b + mod;
  return a - b;
}
long long get_hash1(int ind, int a, int b) {
  if (a == 0) return h1[ind][b];
  return sub(h1[ind][b], pot1[b - a + 1] * h1[ind][a - 1] % p1, p1);
}
long long get_hash2(int ind, int a, int b) {
  if (a == 0) return h2[ind][b];
  return sub(h2[ind][b], pot2[b - a + 1] * h2[ind][a - 1] % p2, p2);
}
int isti(int ind1, int a1, int b1, int ind2, int a2, int b2) {
  return get_hash1(ind1, a1, b1) == get_hash1(ind2, a2, b2) &&
         get_hash2(ind1, a1, b1) == get_hash2(ind2, a2, b2);
}
void precompute() {
  int cnt = 0;
  for (int i = 0; i < n; i++) {
    len[i] = s[i].size();
    for (int j = 0; j < len[i]; j++) {
      cnt++;
      c[i].push_back(cnt);
      h1[i][j] = (s[i][j] + b1 * (j == 0 ? 0 : h1[i][j - 1])) % p1;
      h2[i][j] = (s[i][j] + b2 * (j == 0 ? 0 : h2[i][j - 1])) % p2;
      pot1[j] = (j == 0 ? 1 : b1 * pot1[j - 1]) % p1;
      pot2[j] = (j == 0 ? 1 : b2 * pot2[j - 1]) % p2;
    }
  }
}
void gen(int a, int b) {
  for (int i = 0; i < MAXS; i++) {
    v[i].clear();
  }
  for (int i = a; i <= b; i++) {
    v[0].push_back(c[i][0]);
    for (int j = 0; j < len[i]; j++) {
      for (int k = a; k <= b; k++) {
        if (len[i] - j > len[k]) {
          if (isti(i, j, j + len[k] - 1, k, 0, len[k] - 1)) {
            v[c[i][j]].push_back(c[i][j + len[k]]);
          }
        } else if (len[i] - j < len[k]) {
          if (isti(i, j, len[i] - 1, k, 0, len[i] - 1 - j)) {
            v[c[i][j]].push_back(c[k][len[i] - j]);
          }
        } else {
          if (j != 0 && isti(i, j, len[i] - 1, k, 0, len[k] - 1)) {
            v[c[i][j]].push_back(0);
          }
        }
      }
    }
  }
  return;
  for (int i = 0; i < MAXS; i++) {
    if (v[i].empty()) continue;
    cout << i << "  ";
    for (int j = 0; j < v[i].size(); j++) {
      cout << v[i][j] << " ";
    }
    cout << endl;
  }
}
int dfs(int cvor) {
  bio[cvor] = 1;
  for (int i = 0; i < v[cvor].size(); i++) {
    int sus = v[cvor][i];
    if (bio[sus] == 1) return 1;
    if (bio[sus] == 0 && dfs(sus)) return 1;
  }
  bio[cvor] = 2;
  return 0;
}
int ciklus() {
  memset(bio, 0, sizeof bio);
  for (int i = 0; i < MAXS; i++) {
    if (bio[i] == 0 && dfs(i)) return 1;
  }
  return 0;
}
string rev(string bla) {
  string res = "";
  int lim = bla.size();
  for (int i = 0; i < lim; i++) {
    if (bla[i] == 'a')
      res += 'b';
    else
      res += 'a';
  }
  return res;
}
string fair(int br) {
  string res = "a";
  for (int i = 0; i < br; i++) {
    res = res + rev(res);
  }
  return res;
}
int main() {
  cin >> n;
  for (int i = 0; i < n; i++) {
    cin >> s[i];
  }
  precompute();
  int lef = 0;
  for (int i = 0; i < n; i++) {
    if (lef < i) lef = i;
    while (lef < n) {
      gen(i, lef);
      if (ciklus()) break;
      lef++;
    }
    if (i == lef) continue;
    sol += lef - i;
  }
  cout << sol;
  return 0;
}
