Last week Saraswathi celebrated her 3rd birthday. She received a xylophone as a birthday gift. This xylophone has 8 keys(A,B,C,D,E,F,G,H). Saraswathi started liking the tunes she could produce with that. She does not like certain sequences that make her cry. A tune is unpleasant when it contains a sequence that make her cry. All other tunes are pleasant tunes. Ram her brother who is studying combinatorics in school, wants to find out for a given tune how many distinct non-empty sub tunes exist that are pleasant. Can you help Ram by writing a program that answers his question?
T - Given tune
S - sub tune of the given tune
T - any combination of keys (A,B,C,D,E,F,G,H)
S - where every key used is present in T. If a particular key is present in T K times then you can use that key in S upto K times.
Example 1
T - ABC
S - A, B, C, AB, BA, AC, CA, BC, CB, ABC, ACB, BAC, BCA, CBA, CAB.
Example 2
T - AAB
S - A, B, AA, AB, BA, AAB, ABA, BAA
Input Format
Given Tune
N - (number of tunes that saraswathi dislikes)
N-lines each containing one such tune.
Constraints
Length of the Tune is <= 8
Output Format
Number of pleasant subtunes of the given tune.
Sample Input 0
- AB
- 1
- AB
Sample Output 0
- 3