[2021 SCPC 1차 예선]

친구들

명의 사람들이 좌우로 서 있다. 사람들은 왼쪽에서 순서대로 1번부터 번호가 붙어 있다. 사람들 사이의 친구 관계는 사람들이 들고 있는 자연수를 이용하여 아래 규칙으로 알아낼 수 있다. 아래 규칙에 따라 만들어지지 않는 친구 관계는 없다.



    - 번호 인 사람은 자연수 를 가지고 있다.

    - 번호 인 사람은 번호 인 사람과 친구 관계이다. 친구 관계는 대칭적이다. 즉, 한쪽만 상대방이 친구라고 생각하는 경우는 없다. 만약 번호 인 사람이 존재하지 않는다면, 이 는 무시된다.

    - 사람 가 친구 관계이고 가 친구 관계이면, 도 친구 관계이다.



친구 관계인 극대 그룹은 사람들의 모임인데, 그룹 내의 모든 사람들이 친구 관계이고, 그 조건을 유지하면서 더 이상 사람을 추가할 수 없는 경우를 말한다. 예를 들어 아래와 같이 5명이 각자 가지고 있는 를 표시했다고 하자.







1번 사람과 2번 사람, 2번 사람과 3번 사람이 친구 관계라는 것은 직접 알 수 있다.

규칙에 따라 1번 사람과 3번 사람도 친구 관계이다.

3, 4, 5번 사람이 가지고 있는 수는 무시된다.

그룹 {1번 사람, 3번 사람}을 생각해 보자. 이 그룹 안의 모든 사람은 친구 관계이다.

하지만 2번 사람을 추가해도 모두 친구 관계가 되므로 {1번 사람, 3번 사람}은 친구 관계인 극대 그룹이 아니다.

그룹 {1번 사람, 2번 사람, 3번 사람}은 친구 관계인 극대 그룹이다.

그룹 {1번 사람, 4번 사람, 5번 사람}은 친구 관계가 아닌 쌍이 있으므로 친구 관계인 극대 그룹이 아니다.

친구 관계인 극대 그룹은 {1번 사람, 2번 사람, 3번 사람}, {4번 사람}, {5번 사람}의 3개가 있음을 알 수 있다.



각 사람이 들고 있는 들을 입력 받아 친구 관계인 극대 그룹의 개수를 출력하는 프로그램을 작성하시오.


그림 1

입력

입력 파일에는 여러 테스트 케이스가 포함될 수 있다.

파일의 첫째 줄에 테스트 케이스의 개수를 나타내는 자연수 가 주어지고,

이후 차례로  개의 테스트 케이스가 주어진다.

각 테스트 케이스의 사람들의 수 이 주어진다.

다음 줄에는 왼쪽부터 각 사람들이 들고 있는 자연수가 주어진다. 


출력

각 테스트 케이스의 답을 순서대로 표준출력으로 출력하여야 하며,

각 테스트 케이스마다 첫 줄에는 “Case #”를 출력하여야 한다. 이때 는 테스트 케이스의 번호이다.

그 다음 줄에, 친구 관계인 그룹의 수를 출력하시오.

입출력예

입력
2
5
1 1 3 3 3
10
8 10 5 4 2 5 1 3 1 9
출력
Case #1
3
Case #2
4

돌아가기