Count the mkdir commands needed to create each requested path from its missing prefixes.
Easy3TrieStringInterviewNo attempts yetTime limit5sMemory limit512 MBOn 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?
The first line of the input gives the number of test cases, T. T test cases follow. Each case begins with a line containing two integers N and M, separated by a space.
The next N 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 M 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.
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.