The console one P18540

Jaime wants to do a lot of commands in his console of Linux/Unix/Windows/Mac. All the commands that have to execute have the same shape. The command is formed by a word, that is the name of the program, as for instance cp, mv, etc. Afterwards, different options that are strings of text preceded by a dash without spaces in the middle come, as -R, -verbose, etc. Finally the command has the address of only a file that is referenced with the relative path from the directory where it is or with the absolute path, as for instance, /usr/bin/data.txt, oie/solutions.pdf, ../main.cpp, etc.

Juan wants to do the sequence of commands with the minimal number of pressed keys. To do so, he can use the command cd to change the directory and make the paths shorter. Juan tells you the current path (the directory where he is at the moment) and all the commands that wants to execute. Print the list of commands that Juan should do to minimize the number of pressed keys that Juan must do to write them in his console, counting spaces and returns.

Input

The input will consist of various test data, indicating the number of test data in the first line of the input. Each case will start with a line where will be indicated the number M of commands to execute and a string that will contain the current path where the console of Juan is. Each command will contain a name of command that will be a word formed by lowercase letters and numbers preceded of a dash and the relative or absolute path to a file. The path will be a string that will contain lowercase letters, numbers, bars and dots. Between the commands to execute there will not be any cd, for this reason, the relative paths indicated in the input always are relative with regard to the initial directory where the console of Juan is.

ESTA ES LA EXPLICACIÓN DE LO QUE SON LOS PATHS QUE CLARAMENTE HAY QUE MEJORAR

Un path absoluto es la dirección desde la raíz de la unidad al archivo indicando las diferentes carpetas dónde se encuentra el archivo. Un path relativo indica el camino que se ha de recorrer desde una carpeta hasta otra carpeta o un archivo, pudiendo ir hacia la carpeta padre usando ../. Por ejemplo, si estamos en la carpeta /usr/bin/ y queremos acceder al archivo hola.txt que se encuentra en la carpeta /usr/local, usaremos el path ../hola.txt, o si por ejemplo queremos movernos a la carpeta padre de la que estamos, usaremos el comando cd ../. Obsérvese que los paths absolutos empezarán por el símbolo / mientras que los relativos no. Para realizar un cambio de carpeta se puede usar el path absoluto de la carpeta o también el relativo. Los paths de las carpetas acaban en / mientras que los de los archivos acaban con el nombre del fichero, que será una secuencia de letras minúsculas y caracteres seguidos de un punto y otra secuencia de letras minúsculas y caracteres que indican el tipo del archivo.

Output

For each test data, your program must print the minimal number of pressed keys that must be pressed to execute all the commands in the same order that the order indicated by Juan. The commands must be written in a way that the name, every one of all the options and the file are separated by a space. Moreover, the command cd can be executed many times, but the current directory in the end has to be the same than the initial.

Solution with DP in O(nm) with n the number of command and m the number of different folders.