27532번 - 시계 맞추기

아멜은 벽에 걸어놓을 아날로그 시계 $N$개를 구매하였다. 하지만 일일이 시간을 맞추기 귀찮은 나머지 시계들을 그대로 벽에 걸어버렸다.

시계는 처음에 임의의 시간으로 맞춰져 있었기 때문에 벽에 걸려있는 시계들은 제각기 엉뚱한 시간을 가리키고 있다.

아멜은 어떤 시간 간격마다 시간을 확인하고 기록하는 습관이 있다. 더 구체적으로, $0$보다 큰 정수 $R$에 대해 $R$분에 한 번씩 $N$개의 시계 중 아무거나 하나를 고른 뒤 그 시계가 가리키는 시간을 기록한다.

시계는 아날로그이기 때문에 낮과 밤의 구분이 없다.

아멜이 기록한 일지가 주어졌을 때, 가능한 $N$의 최솟값을 구하여라.

첫째 줄에 일지에 적힌 시간의 개수 $M$이 주어진다. ($1\le M \le 1\,500$)

둘째 줄부터 $M$개의 줄에 걸쳐 일지에 적힌 시간이 HH:MM 형식으로 주어진다. 시간(HH)은 $1$ 이상 $12$ 이하의 정수, 분(MM)은 $0$ 이상 $59$ 이하의 정수로 한 자리 수는 앞에 $0$을 붙여 나타낸다.

가능한 $N$의 최솟값을 출력한다.

• 첫 번째 시계: 1, 3번째 기록
• 두 번째 시계: 2, 5번째 기록
• 세 번째 시계: 4번째 기록

인 경우 $N=3$으로 최적이다.