전광판(marquee)이 별과 우주를 그린 배너 문자열을 한 글자씩 왼쪽으로 밀며 흘려보낸다. 매 프레임마다 배너는 왼쪽으로 정확히 한 칸 회전한다. 즉, 맨 앞 글자가 맨 뒤로 이동한다.

예를 들어 배너가 "..*." 라면

• 1프레임 후: "...*"

• 2프레임 후: "..*."

와 같이 되어, 2프레임 만에 다시 처음과 똑같은 모습이 된다.

배너 문자열 \(S\) 가 주어질 때, 몇 프레임이 지나야 배너가 다시 처음과 완전히 똑같은 모습이 되는지, 그 가장 작은 프레임 수를 출력하라. \(S\) 의 길이를 \(n\) 이라 하면 \(n\) 프레임이 지나면 반드시 원래대로 돌아오므로 답은 항상 \(1\) 이상 \(n\) 이하이다.

\(1 \le n \le 100{,}000\)

\(S\) 는 공백 없이 출력 가능한 ASCII 문자(코드 \(33\)~\(126\))로만 이루어진다.

첫째 줄에 배너의 길이 \(n\) (\(1 \le n \le 100{,}000\)) 이 주어진다.

둘째 줄에 길이 \(n\) 의 배너 문자열 \(S\) 가 주어진다. \(S\) 는 공백을 포함하지 않는, 출력 가능한 ASCII 문자(아스키 코드 33 이상 126 이하)들로 이루어진다.

배너가 다시 처음과 똑같은 모습이 되기까지 필요한 가장 작은 프레임 수를 한 줄에 출력한다.

riseoj 작성

출처 Original