Description
"Mom, don't do that."
You have some secret folders which store a lot of videos about algorithm.
However, you do not want your mom know that you are interested in CS (she wants you to become a doctor).
Thus, you use a special trick to rearrange the original directory and sub-directory so it's difficult to directly access the folder.
Also, you make some fake directories, trying to make your mom more confused.
Although you think it's safe enough, your mom wrote a super program to check whether the decoded directory is valid or not.
Orz.
In order to figure out how your mom does that, you are going to design a similar program.
Given testcases T, each with two strings, O (origin directory) and D (decoded directory), please print "valid" if you can rearrange D into a sub-directory of O; if it's not possible, print "not valid".
Next time, remember to lock your room before leaving home.
hint. You can use string.h to make the problem easier.
Input
The first line of the input is an intger T, denoting the number of testcases. 1<= T <= 100
Next 2*T lines contain information of T pairs of O and D.
O is a directory, composed of a sequence of folders separated by a "/", e.g. "/home/hii/it/is/a/folder".
D is a decoded directory, which may be a sub-directory of O or an invalid directory:
example 1: "/hii/home/it", which is valid because you rearrange it into "/home/hii/it".
example 2: "/hii/it/home/nooo", which is invalid because "nooo" is not a part of folders of O.
1 <= length of O or D <= 5000
1 <= number of folders in O <= 50
Note that O and D must start from a "/", and there is no "/" in the end and each folder may appear more than once.
Output
For each testcases, if D may be valid, print "valid".
Otherwise, print "not valid".
Note that you have to print "\n" after each answer.