There are eight planets and one planetoid in the Solar system. It is not a well known fact that there is a secret planet S4 inhabited by small creatures similar to bears, their codename being Lodas. Although this fact is well hidden from the public, the association Savez sent a team lead by general Henrik to study the Lodas. It has been discovered that Lodas have the ability of teleportation and he wants to hire them in his army.
One Lod consists of
Determine the number of teleportations.
Input Specification
The first line of input contains the integer
In test cases worth 40% of points, it will hold
Output Specification
The first and only line of output must contain the number of teleportations a Loda can make.
Sample Input 1
5
A
B
AA
BBB
AAA
Sample Output 1
3
Explanation for Sample Output 1
Prefix and suffix can intersect so subsequence is
Sample Input 2
5
A
ABA
BBB
ABABA
AAAAAB
Sample Output 2
3
Sample Input 3
6
A
B
A
B
A
B
Sample Output 3
3
Explanation for Sample Output 3
Strings in the subsequence are allowed to be equal so subsequence is
Comments
There is no need to hash for this problem