가르쳐 주세요

Google에서는 서로에게 새로운 기술을 가르쳐 주는 것을 좋아한다! Google에는 1부터 N까지 번호가 매겨진 N명의 직원이 있다. 서로 다른 기술은 총 S개이며, 1부터 S까지 번호가 매겨져 있다. 각 직원은 최대 5개의 서로 다른 기술을 알고 있다.

i번째 직원이 알고 있지만 j번째 직원은 모르는 기술이 하나라도 있으면 i번째 직원은 j번째 직원을 지도할 수 있다. i번째 직원이 j번째 직원을 지도할 수 있는 순서쌍 (i, j)는 몇 개인가?

제한

시간 제한: 테스트 세트당 40초. 메모리 제한: 1GB. 1 ≤ T ≤ 100. 1 ≤ S ≤ 1000. 모든 i에 대해 1 ≤ $C_{i}$ ≤ 5. 모든 i와 j에 대해 1 ≤ $A_{ij}$ ≤ S. 모든 j ≠ k에 대해 $A_{ij}$ ≠ $A_{ik}$.

테스트 세트 1 (공개)

2 ≤ N ≤ 500.

테스트 세트 2 (비공개)

2 ≤ N ≤ 5 × $10^{4}$.

입력의 첫 번째 줄에는 테스트 케이스의 수 T가 주어진다. 이어서 T개의 테스트 케이스가 주어진다. 각 테스트 케이스의 첫 번째 줄에는 두 정수 N과 S가 주어지며, 각각 직원 수와 기술 수를 나타낸다.

다음 N개의 줄에는 각 직원이 알고 있는 기술이 설명된다. 이 중 i번째 줄은 i번째 직원이 알고 있는 기술의 수를 나타내는 정수 $C_{i}$로 시작한다. 이어서 같은 줄에 정수 $C_{i}$개가 주어진다. 이 정수들 중 j번째 정수는 $A_{ij}$이며, 이는 i번째 직원이 기술 $A_{ij}$을 알고 있음을 나타낸다.

각 테스트 케이스마다 Case #x: y을 포함하는 한 줄을 출력한다. 여기서 x는 1부터 시작하는 테스트 케이스 번호이고, y는 i번째 직원이 j번째 직원을 지도할 수 있는 순서쌍 (i, j)의 수이다.

예제 케이스 #1에서:

• (1, 2)는 유효한 쌍이다. 직원 1은 기술 100을 알고 있지만(기술 5와 80도 알고 있다), 직원 2은 이를 모르기 때문이다.

• (1, 3)는 유효한 쌍이다. 직원 1은 기술 100을 알고 있지만(기술 5와 90도 알고 있다), 직원 3은 이를 모르기 때문이다.

• (1, 4)는 유효한 쌍이다. 직원 1은 기술 5을 알고 있지만, 직원 4은 이를 모르기 때문이다.

• (2, 3)는 유효한 쌍이다. 직원 2은 기술 90을 알고 있지만, 직원 3은 이를 모르기 때문이다.

• (3, 2)는 유효한 쌍이다. 직원 3은 기술 80을 알고 있지만, 직원 2은 이를 모르기 때문이다.

• (4, 2)는 유효한 쌍이다. 직원 4은 기술 100을 알고 있지만(기술 80도 알고 있다), 직원 2은 이를 모르기 때문이다.

• (4, 3)는 유효한 쌍이다. 직원 4은 기술 100을 알고 있지만(기술 90도 알고 있다), 직원 3은 이를 모르기 때문이다.

유효한 쌍은 총 7개이므로, 답은 7이다.

예제 케이스 #2에서:

• (1, 3)는 유효한 쌍이다. 직원 1은 기술 10을 알고 있지만(기술 11, 12, 13도 알고 있다), 직원 3은 이를 모르기 때문이다.

• (2, 3)는 유효한 쌍이다. 직원 2은 기술 10을 알고 있지만(기술 11, 12, 13도 알고 있다), 직원 3은 이를 모르기 때문이다.

• (3, 1)는 유효한 쌍이다. 직원 3은 기술 28을 알고 있지만(기술 25, 26, 27, 29도 알고 있다), 직원 1은 이를 모르기 때문이다.

• (3, 2)는 유효한 쌍이다. 직원 3은 기술 27을 알고 있지만(기술 25, 26, 28, 29도 알고 있다), 직원 2은 이를 모르기 때문이다.

유효한 쌍은 총 4개이므로, 답은 4이다.