CFT17

#### Start

2018-05-23 00:00 UTC

## CFT17

#### End

2018-05-24 00:00 UTC
The end is near!
Contest is over.
Not yet started.
Contest is starting in -335 days 10:27:08

24:00:00

0:00:00

# Problem GIncognito

Spies use attributes to disguise themselves to make sure that they are not recognized. For example, when putting on sunglasses, a spy suddenly looks completely different and cannot be recognized anymore. Every combination of attributes gives a different appearance, but not all combinations are possible. For example, a hat and a turban are both headgear and cannot be used at the same time. Given the list of available attributes, compute how many distinct disguises can be made.

## Input

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.

## Output

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

5