The ancient Berlanders believed that the longer the name, the more important its bearer is. Thus, Berland kings were famous for their long names. But long names are somewhat inconvenient, so the Berlanders started to abbreviate the names of their kings. They called every king by the first letters of its name. Thus, the king, whose name was Victorious Vasily Pupkin, was always called by the berlanders VVP.

In Berland over its long history many dynasties of kings replaced each other, but they were all united by common traditions. Thus, according to one Berland traditions, to maintain stability in the country, the first name of the heir should be the same as the last name his predecessor (hence, the first letter of the abbreviated name of the heir coincides with the last letter of the abbreviated name of the predecessor). Berlanders appreciate stability, so this tradition has never been broken. Also Berlanders like perfection, so another tradition requires that the first name of the first king in the dynasty coincides with the last name of the last king in this dynasty (hence, the first letter of the abbreviated name of the first king coincides with the last letter of the abbreviated name of the last king). This tradition, of course, has also been always observed.

The name of a dynasty is formed by very simple rules: we take all the short names of the kings in the order in which they ruled, and write them in one line. Thus, a dynasty of kings "ab" and "ba" is called "abba", and the dynasty, which had only the king "abca", is called "abca".

Vasya, a historian, has recently found a list of abbreviated names of all Berland kings and their relatives. Help Vasya to find the maximally long name of the dynasty that could have existed in Berland.

Note that in his list all the names are ordered by the time, that is, if name A is earlier in the list than B, then if A and B were kings, then king A ruled before king B.

Input

The first line contains integer n (1 ≤ n ≤ 5·105) — the number of names in Vasya's list. Next n lines contain n abbreviated names, one per line. An abbreviated name is a non-empty sequence of lowercase Latin letters. Its length does not exceed 10 characters.

Output

Print a single number — length of the sought dynasty's name in letters.

If Vasya's list is wrong and no dynasty can be found there, print a single number 0.

Examples

Input

3
abc
ca
cba


Output

6


Input

4
vvp
vvp
dam
vvp


Output

0


Input

3
ab
c
def


Output

1

Note

In the first sample two dynasties can exist: the one called "abcca" (with the first and second kings) and the one called "abccba" (with the first and third kings). 

In the second sample there aren't acceptable dynasties.

The only dynasty in the third sample consists of one king, his name is "c".

import java.io.BufferedReader;
import java.io.FileNotFoundException;
import java.io.InputStreamReader;
import java.io.PrintWriter;
import java.util.Arrays;
import java.util.StringTokenizer;

/**
  50 agecd cghafi fiide iecc jbdcfjhgd diee hfeg ehc gfijgjh gacaifebg dicbbddc
  hjgciaei jjcdh g gc cf hfdjhd c icidbec ji eeh cgeejggc acfd jjg ajefdj
  eghhebiic bih gbb jjaa idc gafi ecg dbigbjiehj cedif ahidfaaajg hfhhiccbgb
  dgegjgieif hgjebhfdc j ahehd ahdah bijbhh a dabiggfhac dedigbjbf ihbdj
  iihagchd gfebhfdi jbjdcggdh f
 *
 * @author pttrung
 */
public class A {

    //  public static int[][] dp;
    public static int Mod;

    public static void main(String[] args) {
        try {
            Scanner in = new Scanner();
            // PrintWriter out = new PrintWriter(new FileOutputStream(new File("output.txt")));
            PrintWriter out = new PrintWriter(System.out);
            // System.out.println(Long.MAX_VALUE);

            int n = in.nextInt();
            String[] data = new String[n];
            int[][] dp = new int[26][26];
            for (int i = 0; i < n; i++) {
                data[i] = in.next();
            }

            for (int i = n - 1; i >= 0; i--) {
                int s = data[i].charAt(0) - 'a';
                int e = data[i].charAt(data[i].length() - 1) - 'a';
                //dp[s][e] = Math.max(dp[s][e], data[i].length());
                for (int j = 0; j < 26; j++) {
                    if (dp[e][j] > 0) {
                        dp[s][j] = Math.max(data[i].length() + dp[e][j], dp[s][j]);
                    }
                }
                dp[s][e] = Math.max(dp[s][e], data[i].length());
            }
            int result = 0;
            for (int i = 0; i < 26; i++) {
                //System.out.println(i + " " + dp[i][i]);
                result = Math.max(dp[i][i], result);
            }
            out.println(result);

            out.close();
        } catch (Exception ex) {
            ex.printStackTrace();
        }
    }

    public static class Node implements Comparable<Node> {

        int index, val;

        public Node(int index, int val) {
            this.index = index;
            this.val = val;
        }

        @Override
        public int compareTo(Node o) {
            if (val != o.val) {
                return val - o.val;
            }
            return index - o.index;
        }
    }

    public static int[][] powSquareMatrix(int[][] A, long p) {
        int[][] unit = new int[A.length][A.length];
        for (int i = 0; i < unit.length; i++) {
            unit[i][i] = 1;
        }
        if (p == 0) {
            return unit;
        }
        int[][] val = powSquareMatrix(A, p / 2);
        if (p % 2 == 0) {
            return mulMatrix(val, val);
        } else {
            return mulMatrix(A, mulMatrix(val, val));
        }

    }

    public static int[][] mulMatrix(int[][] A, int[][] B) {
        int[][] result = new int[A.length][B[0].length];
        for (int i = 0; i < result.length; i++) {
            for (int j = 0; j < result[0].length; j++) {
                long temp = 0;
                for (int k = 0; k < A[0].length; k++) {

                    temp += ((long) A[i][k] * B[k][j] % Mod);
                    temp %= Mod;
                }
                temp %= Mod;
                result[i][j] = (int) temp;
            }
        }

        return result;
    }

    static double dist(Point a, Point b) {
        long total = (a.x - b.x) * (a.x - b.x) + (a.y - b.y) * (a.y - b.y);
        return Math.sqrt(total);
    }

    static class Point implements Comparable<Point> {

        int x, y;

        public Point(int x, int y) {
            this.x = x;
            this.y = y;

        }

        @Override
        public int compareTo(Point o) {
            if (x != o.x) {
                return x - o.x;
            }
            return y - o.y;
        }
    }

    public static boolean nextPer(int[] data) {
        int i = data.length - 1;
        while (i > 0 && data[i] < data[i - 1]) {
            i--;
        }
        if (i == 0) {
            return false;
        }
        int j = data.length - 1;
        while (data[j] < data[i - 1]) {
            j--;
        }
        int temp = data[i - 1];
        data[i - 1] = data[j];
        data[j] = temp;
        Arrays.sort(data, i, data.length);
        return true;
    }

    static class FT {

        int[] data;

        FT(int n) {
            data = new int[n];
        }

        void update(int index, int val) {
            // System.out.println("UPDATE INDEX " + index);
            while (index < data.length) {
                data[index] += val;
                index += index & (-index);

                //    System.out.println("NEXT " +index);
            }
        }

        int get(int index) {
            //  System.out.println("GET INDEX " + index);
            int result = 0;
            while (index > 0) {
                result += data[index];
                index -= index & (-index);
                // System.out.println("BACK " + index);
            }
            return result;
        }
    }

    static int gcd(int a, int b) {
        if (b == 0) {
            return a;
        } else {
            return gcd(b, a % b);
        }
    }

    static int pow(int a, int b) {
        if (b == 0) {
            return 1;
        }
        if (b == 1) {
            return a;
        }
        int val = pow(a, b / 2);
        if (b % 2 == 0) {

            return val * val;
        } else {
            return val * val * a;
        }
    }

//    static Point intersect(Point a, Point b, Point c) {
//        double D = cross(a, b);
//        if (D != 0) {
//            return new Point(cross(c, b) / D, cross(a, c) / D);
//        }
//        return null;
//    }
//
//    static Point convert(Point a, double angle) {
//        double x = a.x * cos(angle) - a.y * sin(angle);
//        double y = a.x * sin(angle) + a.y * cos(angle);
//        return new Point(x, y);
//    }
//    static Point minus(Point a, Point b) {
//        return new Point(a.x - b.x, a.y - b.y);
//    }
//
//    static Point add(Point a, Point b) {
//        return new Point(a.x + b.x, a.y + b.y);
//    }
//
//    static double cross(Point a, Point b) {
//        return a.x * b.y - a.y * b.x;
//
//
//    }
//
//    static class Point {
//
//        int x, y;
//
//        Point(int x, int y) {
//            this.x = x;
//            this.y = y;
//        }
//
//        @Override
//        public String toString() {
//            return "Point: " + x + " " + y;
//        }
//    }
    static class Scanner {

        BufferedReader br;
        StringTokenizer st;

        public Scanner() throws FileNotFoundException {
            //System.setOut(new PrintStream(new BufferedOutputStream(System.out), true));
            br = new BufferedReader(new InputStreamReader(System.in));
            //br = new BufferedReader(new FileReader(new File("input.txt")));
        }

        public String next() {


            while (st == null || !st.hasMoreTokens()) {
                try {
                    st = new StringTokenizer(br.readLine());
                } catch (Exception e) {
                    throw new RuntimeException();
                }
            }
            return st.nextToken();
        }

        public long nextLong() {
            return Long.parseLong(next());
        }

        public int nextInt() {
            return Integer.parseInt(next());
        }

        public double nextDouble() {
            return Double.parseDouble(next());
        }

        public String nextLine() {
            st = null;
            try {
                return br.readLine();
            } catch (Exception e) {
                throw new RuntimeException();
            }
        }

        public boolean endLine() {
            try {
                String next = br.readLine();
                while (next != null && next.trim().isEmpty()) {
                    next = br.readLine();
                }
                if (next == null) {
                    return true;
                }
                st = new StringTokenizer(next);
                return st.hasMoreTokens();
            } catch (Exception e) {
                throw new RuntimeException();
            }
        }
    }
}