부정직한 운전기사

파리 샤를 드골 공항에 도착한 당신은 "경쟁력 있는 가격"을 제안한 무허가 운전기사의 차를 순진하게 탔습니다. 결과는 참혹했습니다. 가격이 터무니없이 비쌌을 뿐만 아니라, 기사는 그 가격을 정당화하려고 필요 이상으로 여정을 길게 돌았습니다.

당신이 이 사기를 눈치챈 이유는 같은 장소를 여러 번 지나갔기 때문입니다. 당신의 기억력은 아주 좋아서, 사기꾼이 강제로 돌게 한 각각의 순환까지 포함해 자신이 지나온 경로를 아주 잘 기억하고 있습니다.

이제 당신은 이 운전기사를 고소하려고 경찰서에 왔고, 경찰관이 당신에게 사연을 말해 달라고 요청합니다. 경찰관은 당신이 지나온 경로의 모든 세부 사항까지 알려 달라고 합니다. 또 두어 시간을 낭비하고 싶지 않은 당신은 이 경로를 압축한 형태로 알려 주기로 합니다.

당신이 장소 A, B, C, D, A, B, C, D를 지났다고 기억한다고 합시다. 이때 당신은 "경로 ABCDABCD를 지났습니다"라고 말하기보다 "경로 ABCD를 두 번 지났습니다"라고 말하는 편을 선호합니다. 경로가 같은 장소 순서를 반복했으므로, 세부 사항을 하나도 빠뜨리지 않고 진술을 크게 줄일 수 있습니다.

더 정확히는, 지나온 장소의 목록을 입력으로 받아 이 경로의 가장 짧은 압축 형태의 크기를 반환하는 프로그램을 작성해야 합니다. 압축된 경로는 다음 중 하나입니다.

• 지나온 장소 하나. 이를 "원자 경로"라고 합니다.
• 압축된 경로 두 개의 연결.
• 압축된 경로의 반복, 즉 (C)n. 이는 C가 나타내는 경로를 n번 연속으로 지났다는 뜻입니다.

압축된 경로의 크기는 그것에 포함된 원자 경로의 개수로 정의합니다.

입력은 두 줄로 이루어집니다.

• 첫째 줄에는 정수 N, 즉 경로의 길이가 주어집니다.
• 둘째 줄에는 길이 N의 문자열로 표현된 경로가 주어집니다. 각 장소는 영숫자 문자 하나로 표현합니다. 즉 숫자('0'부터 '9'), 소문자('a'부터 'z'), 대문자('A'부터 'Z') 중 하나입니다.

한 줄에 정수 하나를 출력합니다. 이는 가장 짧은 압축 경로의 크기입니다.

• 0 < N ≤ 700