문제 설명
KOREATECH에서 제 6회 강강술래 대회를 개최하기로 하였다.
이 대회의 조직위원이된 종욱이는 광성, 영준, 재우와 함께 대회에 참석한 선수들을 다음의 규칙에 따라 그룹을 짓기로 하였다.
강강술래를 그룹을 짓는 규칙
1. 대회에 참석하는 각 선수는 고유의 번호를 부여받게 된다. 가령 A라는 선수가 2번이면 다른 누구도 2번 숫자를 부여받지 않는다.
2. 그룹은 두 선수 간의 1을 제외한 공약수가 하나라도 있으면 그룹으로 만들어준다. 가령 4번, 6번 선수는 2가 공약수이고 6번, 15번 선수는 3이 공약수이며 15번 35번 선수는 5가 공약수 이므로 4-6-15-35번 선수는 하나의 그룹으로 그룹지을 수 있다.
3. 이때 각 선수들에게 부여되는 번호의 범위와 참석 인원의 범위는 다음과 같다.
1 <= A.size() <= 20,000
1 <= A[i] <= 100,000
이렇게 구성된 그룹들 중 가장 많은 선수들로 이루어진 그룹의 크기는 얼마일까?
입력 설명
첫 줄에는 테스트 케이스의 개수 T(1 <= T <= 15)가 주어진다.
그 다음 각 테스트 케이스 별로 한줄에 걸처 첫 번째는 입력의 갯수가 (1 <= A.size() <= 20,000) 그 이후로는입력의 갯수 만큼의 정수 (1 <= A[i] <= 100,000)가 주어진다.
출력 설명
테스트 케이스마다 가장 큰 그룹의 수를 출력한다.
입력 예시 Copy
3
4 4 6 15 35
4 20 50 9 63
8 2 3 6 7 4 12 21 39
출력 예시 Copy
4
2
8
도움
4 6 15 35
20 50 9 63
2 3 6 7 4 12 21 39
