[String] 9375번 - 패션왕 신해빈(53일차)

#코드 실행 시간 단축
import sys
input = sys.stdin.readline

#입력받은 수만큼 반복
for _ in range(int(input())):
    #의상의 개수 입력
    N = int(input())

    #의상 종류와 해당 종류 의상의 개수를 저장하는 딕셔너리
    cloth = {}

    #의상 이름과 종류 입력 후 딕셔너리 저장
    #중요한 것은 의상 이름이 아니라 각 종류의 의상 개수이므로 새로운 의상에 대해 +1
    for i in range(N):
        name, wear = input().split()
        try:    
            cloth[wear] += 1
        except:
            cloth[wear] = 1
    
    #종류별 의상의 개수를 list로 추출
    name_wear = list(cloth.values())

    #의상 조합의 개수를 1에서 시작
    #의상이 없는 경우가 있을 수 있으므로 나중에 -1을 해줘야 함
    cnt = 1

    #종류별 의상 개수에 대해
    for w in name_wear:
        #의상 개수 +1을 기존 조합의 수에 곱함
        #조합의 개수
        #1. 해당 종류에서 옷 선택하는 경우: n개
        #2. 해당 종류에서 옷을 선택하지 않는 경우 1개
        cnt *= (w+1)
    
    #의상이 0개인 경우 처리를 위해 -1
    #의상이 1개 이상인 경우, 아무것도 입지 않는 경우 제거를 위해 -1
    print(cnt-1)

#인사이트
#모든 조합을 도출해야 한다는 생각에 섣부르게 combination을 사용
#확률과 통계적 사고를 조금 했다면, 선택하지 않는 경우를 고려해서 쉽게 풀 수 있었던 문제
#자리 배분 및 팀 선택과 유사한 유형