On the first line one positive number: the number of test cases, at most 100. After that per test case:
one line with an integer $n$ ($0\le n \le 30$): the number of available attributes.
$n$ lines with two space-separated strings: the name and the category of the attribute.
All strings consist of at least $1$ and at most $20$ lowercase letters. Within a test case all names are distinct.
Per test case:
one line with an integer: the number of possible distinct disguises that can be made with the given attributes, such that at most one attribute from each category is used.
|Sample Input 1||Sample Output 1|
2 3 hat headgear sunglasses eyewear turban headgear 3 mask face sunglasses face makeup face