A “letter” lock is a circle, in which we mark some positions equidistant from one another. The positions are numbered clockwise by a zero-based index and there is exactly one En- glish capital letter put in each position. The state of the lock is given by a string, which con- tains all letters enumerated from position 0 to the end. The lock can change its state by per- forming rotations: After a rotation, every letter in the circle will move clockwise to the next po- sition. If the lock received a password in form of a string, it will step by step rotate to change its state and verify whether its current state matches the prefix of the password. Whenever it matches, the lock will be unlocked, and the verification process will stop successfully. If the lock moves around and there has been no matched state found, it will delete the first character in the password and retry with the new password, and so on. This process repeats until the lock is unlocked or the password has been completely deleted (verification fails). Given a sequence of N locks, in which the state of any lock is not shorter than the state of its previous lock, one may want to unlock all of them in succession by only one password. The process is as follows: the password is first applied to the first lock in the sequence; the remaining password after unlocking the first lock will be applied again to the second lock, the remaining password after unlocking the second lock will be applied again to the third lock, etc. The process continues until the last lock is unlocked. Your task is to write a program to find the shortest password (in terms of the number of characters) that can be used to unlock all these N locks in succession. If there is more than one solution, just find the first one in lexicographic order. Input The input file consists of several data sets. The first line of the input file contains the number of data sets which is a positive integer and is not bigger than 20. The following lines describe the data sets. For each data set, there is only one line containing a string that lists all states of the locks separated by one semicolon (‘;’). In each test case, the number of locks is not greater than 200, the state of every lock is not empty and consists of less than 101 letters. Output For each test case, write in one line the shortest password to unlock all the locks in succession. Sample Input 3 TOPO;POFTTO;THEPOF;HEWOOFT;HEWORLDT WELC;COMEEL;METLCO;TOCOME HEACMT;PROGRAMCM;RAMMINGCON;CONTESTING
2/2 Sample Output TOPOFTHEWORLD WELCOMETO THEACMPROGRAMMINGCONTEST