PC4D - Names

Sattu has N number of friends. One day she decided to make a graph that will represent the names of all her friends. The graph has 26 nodes [A – Z] and is undirected. She followed the following rules to construct the graph:

  1. Draw an edge between the adjacent letters in the name. For e.g. If the name is JOJO, we add an edge b/w J and O.
  2. Never draw an edge twice. For e.g. If name is JOJO, the complete name can be represented with one edge only. (J – O).
  3. Draw a self edge if two adjacent letters are same. For example in FOO we have two edges – One between F and O, and other is a self edge (O-O).

Now you are given the list of friends of Sattu. You have to find out the minimum number of edges required to represent all the names in an undirected graph.

Input

First line will contain a value N – Number of friends Sattu has. (1 <= N <= 1000)

Next N lines will contain the names of Sattu’s Friends.

All names are one word string of uppercase alphabets and their length is less than 20.

Output

Minimum number of edges required to draw the graph.

Example

Input:
4
ABHU
SATTU
SUBBU
CHOTU

Output:
13

Added by:Rajesh Kumar
Date:2013-02-10
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All

© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.