암호학자의 골칫거리

KTH 이론 컴퓨터과학 연구실 복도의 벽은 거의 전부 화이트보드다. 연구실 사람 중에는 암호학자가 여럿 있고, 이들은 화이트보드에 암호 퍼즐을 적어 두기를 좋아한다. 누군가 앞선 퍼즐의 답을 찾아내면 새 퍼즐이 하나 올라온다.

2주 전에 페르가 복도를 지나갈 때 가장 최근에 올라온 퍼즐은 GuvfVfNGrfg였다. 자리로 돌아온 페르는 이것이 ThisIsATest를 ROT13으로 암호화한 문자열이라는 것을 금방 알아냈다.

시시한 퍼즐은 다음 주에도 이어졌다. 새로 올라온 퍼즐은 VmkgdGFyIHPDpGtlcmhldGVuIHDDpSBzdMO2cnN0YSBhbGx2YXIK였는데, 이번에는 그냥 base64로 인코딩한 문장이었다. 장난은 이쯤이면 됐다고 생각한 페르는 본때를 보여주기로 했다.

페르의 계획은 이렇다. 하루에 암호문에서 글자 하나를 지우고 다른 글자로 바꿔 적는다. 그렇게 해서 마지막에는 전체가 PerPerPerPerPerPerPer처럼 자기 이름만 반복되도록 만든다. 하루에 한 글자씩만 바꾸니 아무도 눈치채지 못하리라 기대한다.

주어진 암호문을 자기 이름만 반복되는 문자열로 바꾸는 데 며칠이 걸리는지 페르는 알고 싶다. 원래 암호문의 길이는 3의 배수라고 가정해도 된다.

편의상 대소문자는 구분하지 않고, 모든 글자가 대문자라고 생각한다.

첫째 줄에 화이트보드에 적힌 암호문이 주어진다. 암호문은 대문자로만 이루어져 있고, 길이는 300 이하이면서 3의 배수다.

암호문을 페르의 이름만 반복되는 문자열, 즉 PER를 이어 붙인 문자열로 바꾸는 데 필요한 날수를 출력한다.