Fashion King Haebin

Interview

Time limit1sMemory limit128 MB

Summary

Count all nonempty outfits by picking at most one item from each clothing kind.

Level: Easy3 of 10
Topics: Combinatorics, Hash map
Solved: No attempts yet

Problem

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.

Input

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.

Output

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

Hint

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.

Examples1

Example 1

Input

2
3
hat headgear
sunglasses eyewear
turban headgear
3
mask face
sunglasses face
makeup face

Expected output

5
3