Інкогніто
Шпигуни використовують різні атрибути, щоб замаскуватися і залишатися невпізнаними. Наприклад, одягнувши сонцезахисні окуляри, шпигун може виглядати зовсім інакше, і його вже не можна впізнати. Кожна комбінація атрибутів створює новий вигляд, але не всі комбінації можливі.
Наприклад, капелюх і тюрбан - це обидва головні убори, тому їх не можна використовувати одночасно. Враховуючи список доступних атрибутів, обчисліть, скільки різних маскувань можна створити.
Вхідні дані
На першому рядку міститься одне додатне число: кількість тестових випадків, не більше 100. Далі, для кожного тестового випадку:
один рядок з цілим числом n (0 ≤ n ≤ 30): кількість доступних атрибутів.
n рядків, кожен з двома словами, розділеними пробілом: назва і категорія атрибуту.
Усі рядки складаються щонайменше з 1 і щонайбільше з 20 малих літер. У межах одного тестового випадку всі назви є унікальними.
Вихідні дані
Для кожного тестового випадку:
один рядок з цілим числом: кількість можливих різних маскувань, які можна створити з даними атрибутами, так що використовується не більше одного атрибуту з кожної категорії.