Page not loading? Try clicking here.
Placeholder

#3699

Spy 1s 256MB

Problems

Jungol is a spy.

As a master of disguise, he never goes out wearing the same combination of clothes as the previous day.

For example, if he wore glasses, a coat, and shoes yesterday, today he might wear sunglasses instead of glasses, or add pants, etc.

Write a program that, given the clothes (including accessories) Jungol owns, calculates the number of possible days he can go outside wearing at least one item of clothing.

Example

Suppose Jungol has the following 3 items:

hat headgear
sunglasses eyewear
turban headgear

  • The headgear category includes hat and turban.

  • The eyewear category includes sunglasses.

Then the following 5 combinations are possible:

  1. hat

  2. turban

  3. sunglasses

  4. hat + sunglasses

  5. turban + sunglasses


Input

The first line contains the number of test cases TC (1 ≤ TC ≤ 100).

For each test case:

  • The first line contains the number of items N (0 ≤ N ≤ 30) Jungol owns.

  • The next N lines each contain two strings: the item name and its category name.

Notes:

  • Each string has a length between 1 and 20.

  • Item names are unique.


Output

For each test case, print the maximum number of days Jungol can go outside wearing at least one piece of clothing.


Example 

2

3

hat headgear

sunglasses eyewear

turban headgear

3

mask face

sunglasses face

makeup face
5

3


Source

BAPC 2013 I번 incognito

You must sign in to write code.