슬픔도, 분노도. 전부 인수분해해주겠어.

베리타스 부원이 내가 잠든 사이에 해야하는 일을 마무리해 주었어. 이제 남은건 노아가 전달해준 기자재 관리 계획 세우기만 남았어. 이것만 빠르게 계산하고 대운동회 준비를 마치자.

각 종목에 쓸 체육 기자재 묶음에 $1$번부터 $N$번까지 번호를 붙여두었어. 그러면 기자재 조합으로 하나의 운동 경기 $G$를 개최할 수 있을거야.

운동 경기 $G$는 다음 조건을 만족해야 해.

• 서로 다른 번호의 기자재를 두 개 이상 사용해야 운동 경기 $G$를 열 수 있다.
• 운동 경기 $G$에 사용되는 서로 다른 기자재 두 개를 선택하더라도 기자재 번호의 최대공약수는 $K$여야 한다.

이제 운동 경기 $G$ 여럿으로 구성된 운동회 계획 $P$를 만들어야 해. 그런데 이 운동회 계획 $P$에는 만족해야 하는 조건이 있어서 머리가 아픈데, 메모로 정리해볼까?

• 운동회 계획 $P$에서 동일한 기자재 조합으로 두 개 이상의 운동 경기를 열 수 없다.
• 운동회 계획 $P$에 포함되는 임의의 운동 경기 $G$에 대해, $G$보다 더 많은 기자재를 사용하는 운동 경기가 하나 이상 존재한다면, 그러한 운동 경기의 목록을 $G'_1$, , , 이라고 하자. 운동 경기 에서 사용하는 기자재를 모두 사용하는 운동 경기 가 적어도 하나 이상 운동회 계획 에 존재한다.

운동 경기 $G$를 최대한 많이 포함하는 운동회 계획 $P$을 생각하자. 그러한 운동회 계획 $P$은 몇 개의 운동 경기 $G$를 포함하는지 궁금하다라.. 노아가 말해준 일거리이긴 한데.. 이거, 아무리 들어도 황륜대제 기자재 관리 계획이 아니라 그냥 알고리즘 문제 같은데? 잠깐만! 노아! 어디갔어!?

$G_4$보다 더 많은 기자재를 사용한 운동 경기는 존재하지 않으므로, $G_4$는 운동회 계획 $P$에 포함될 수 있다.

운동 경기 $G_1, G_2, G_3$보다 더 많은 기자재를 사용한 $G_4$가 존재한다.

$G_1 \subset G_4, G_2 \subset G_4, G_3 \subset G_4$이므로 $G_1, G_2, G_3$은 운동회 계획 $P$에 포함될 수 있다.

따라서 운동회 계획 $P$에 포함된 운동 경기의 수는 $4$이다.

시간 제한

1000 ms

메모리 제한

1024 MB

체커

CUSTOM