Fashion King Haebin

Haebin cares a lot about fashion and never wears the same combination of clothes twice. For example, if Haebin wears glasses, a coat, a shirt and shoes today, then tomorrow something has to change: add trousers, or swap the glasses for contact lenses.

Given the clothes Haebin owns, work out how many days in a row Haebin can go outside without being naked.

The first line contains the number of test cases, which is at most 100.

• The first line of each test case contains $n$ ($0 \le n \le 30$), the number of clothes Haebin owns.
• Each of the next $n$ lines contains the name and the kind of one item, separated by a space. Haebin can wear only one item of each kind at a time.

Every string is 1 to 20 lowercase letters long, and no two items in the same test case share a name.

For each test case, print the number of distinct outfits Haebin can wear without being naked, one per line.

If the items of kind headgear are hat and turban, and the only item of kind eyewear is sunglasses, the possible outfits are (hat), (turban), (sunglasses), (hat, sunglasses) and (turban, sunglasses), so the answer is 5.