Stamp timer 1s memory 256MB

헌이는 Petrr와 원석이가 담장에 일루 절루 페인트 칠을 하는 것을 보고 너무 에너지 낭비란 생각이 들었다. 

헌이는 디자인에 관심이 많기 때문에 먼저 담장의 각 칸에 어떤 색을 칠할지 정해 놓았다. 

색은 1 이상 26이하의 총 26가지가 있다. 그런데, 담장이 너무 길기 때문에 이걸 일일이 칠하려면 꼬박 10만년이 걸린다고 한다.

헌이는, 특수 담장용 도장을 미리 제작해서, 이 도장으로 담장 페인트 칠을 하려 한다.

예를 들어 아래와 같이 2가지 색으로 담장에 페인트 칠을 하고 싶다고 해보자.

  헌이가 이 담장와 똑같은 길이 8짜리 특수 도장을 만들고 같은 색을 입힌 다면, 담장에 똑같이 칠할 수 있다. 

하지만 길이 5짜리 도장으로도 같은 일을 할 수 있다.

더 짧은 길이의 도장으로는 이 일을 할 수 없다. 도장으로 담장에 페인트 칠을 할 때에는 아래와 같은 규약이 있기 때문이다

1. 도장은 좌우가 정해져 있다. 즉 색깔이 RGRRG인 도장을 만들었으면 RGRRG인 색만 칠할 수 있고, GRRGR은 칠할 수 없다.
2. 색을 겹쳐서 도장을 찍을 때에는, 어떤 색 위에 다른 색을 덧칠하면 안 된다. 색이 번지기 때문이다. 위의 예에서는 4번째 칸과 5번째 칸에 같은 색이 칠해져 있기 때문에 겹쳐서 도장을 찍을 수 있다.
3. 담장을 벗어나게 페인트 칠을 하면 안 된다.

최소 길이 몇 짜리의 도장을 만들어야 헌이가 원하는 일을 할 수 있는지 알아보자.