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