Preparing NOJ

Text Messaging

1000ms 65536K

Description:

You can type alphabets on a cell phone using numeric keypads using the following key mapping.

 Numbers Alphabets 2 abc 3 def 4 ghi 5 jkl

 Numbers Alphabets 6 mno 7 pqrs 8 tuv 9 wxyz

Since one numeric keypad represents many alphabets, on the standard system, the user must press the keypad many times to choose the right alphabet. For example to type the word “rat”, the user must press 77728. (777 to get “r”, 2 to get “a”, and 8 to get “t”.)

After the word prediction software, the user does not have to do that anymore. To type “rat” the user can type 728, and the prediction software would guess “rat” automatically. For another example, consider the word “cat.” To type that the user needs only press 228. We call the key sequence required to type a given word as its key sequence. Thus, the key sequence of “cat” is 228, and the key sequence of “rat” is 728.

However, this is not perfect because many words share the same key sequence. For example, “cat” and “bat” have the same key sequence 228.

Given a set of words, your task is to find out how many different key sequences needed to type any words in the set. For example if the set is {“rat”, “cat”, “bat”}, the number of different key sequences is 2, i.e., 228 and 728.

Input:

The first line of the input contains an integer T (1 <= T <= 6) denoting the number of test cases. After that T test cases follow.

The first line of each test case contains an integer N (1 <= N <= 1,000) denoting the number of words. After that N lines follows. Each line contains different word. Each word consists of only small English alphabets, and the maximum length of any words is at most 20 characters.

Output:

For any test case, your program should output an integer K denoting the number of different key sequences.

Sample Input:

23catratbat5abcdefgcccdddiaaafefhhelloworld

Sample Output:

23

Note:

In the first case, two sequences are 228 and 728. In the second case, the three sequences are 2223334, 43556, and 96753.

Info

Provider NOJ

Code NOJ1464

Tags

Submitted 1

Passed 1

AC Rate 100%

Date 04/20/2019 10:03:10

Related

Nothing Yet