Թաքցված խնդիր
|Այս խնդիրը թաքցված է խմբագրական խրհրդի անդամի կողմից քանի որ կամ այն ոչ ճիշտ լեզվով է գրված,|կամ թեստային տվյալներն են սխալ, կամ խնդրի ձևակերպումը պարզ չէ։|

ACM_0041 - INCOGNITO

   Spies use attributes to disguise themselves to make sure that they are not recognized. For example, when putting on sun- glasses, 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 n 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.

Examples

stdin

stdout

1

2

3

hat headgear

sunglasses eyewear

turban headgear

3

mask face

sunglasses face

makeup face

5

3


Ավելացրեց.Հրանտ Հովհաննիսյան
Ամսաթիվ.2013-12-25
Ժամանակի սահմանափակումը.1s
Ծրագրի տեքստի սահմանափակումը.50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Լեզուներ.Բոլորը բացի ASM32 ASM64 GAWK CLPS CLOJURE D ERL FSHARP FORTRAN GOSU HASK ICON ICK NEM NIM OBJC-CLANG PICO PIKE PYPY PY_NBC RUST SCM guile CHICKEN SED TCL WHITESPACE
Աղբյուրը.Benelux (BAPC) 2013.I

© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.