File Fix-it (Small)

Count the mkdir commands needed to create each requested path from its missing prefixes.

Easy3TrieStringInterviewNo attempts yetTime limit5sMemory limit512 MB

Problem

On Unix computers, data is stored in directories. There is one root directory, and it can contain several directories, each with a different name. Those directories can contain more directories, and so on.

A directory is identified by its name together with its parent directory, the directory that directly contains it. A path encodes this as several parts, each preceded by a forward slash ('/'). The last part is the name of the directory itself, and everything before it is the path of the parent directory. For example, consider this path:

/home/gcj/finals

It refers to the directory named "finals" inside the directory described by "/home/gcj", which in turn refers to the directory named "gcj" inside the directory described by "/home". The path "/home" has only one part, so it refers to the directory named "home" in the root directory.

The mkdir command creates a directory. You give it a path, and mkdir creates the directory described by that path, but only if the parent directory already exists. To create "/home/gcj/finals" and "/home/gcj/quals" from scratch you need four commands:

mkdir /home
mkdir /home/gcj
mkdir /home/gcj/finals
mkdir /home/gcj/quals

Given every directory that already exists on your computer and a set of directories you want to create if they do not exist yet, how many mkdir commands do you need?

Input

The first line of the input gives the number of test cases, TT. TT test cases follow. Each case begins with a line containing two integers NN and MM, separated by a space.

The next NN lines each give the path of one directory that already exists on your computer. This list contains every directory already on the computer except the root directory. (The root directory is on every computer, so it is never listed.)

The next MM lines each give the path of one directory you want to create.

Every path in the input uses the format described above. A path is one or more lower-case alphanumeric strings (containing only 'a' to 'z' and '0' to '9'), each preceded by a single forward slash. These strings are never empty.

Limits

  • 1T1001 \le T \le 100
  • No path is longer than 100 characters.
  • No path appears twice in the list of directories already on the computer, and no path appears twice in the list of directories you want to create. The same path may appear once in each of the two lists.
  • If a directory is listed as already existing, its parent directory is listed too, unless the parent is the root directory.
  • The whole input is at most 100,000 bytes.
  • 0N100 \le N \le 10
  • 1M101 \le M \le 10

Output

For each test case, print one line containing "Case #x: y", where x is the case number starting from 1 and y is the number of mkdir commands you need.