샹들리에

Lamps-O-Matic 사는 아주 큰 샹들리에를 조립한다. 샹들리에는 여러 층으로 이루어진다. 첫 번째 층에서는 고리(ring)에 크리스털 펜던트를 매단다. 이렇게 조립한 고리들과 새 펜던트들을 다음 층의 고리에 매달고, 이 과정을 반복한다. 마지막에는 큰 고리 하나만 남는데, 그 아래에 여러 개의 작은 고리와 펜던트가 매달린 완성된 샹들리에다.

전용 조립 로봇이 샹들리에를 만든다. 로봇에게는 크리스털 펜던트와 빈 고리가 무한히 있고, 조립 도중 부품을 담아 두는 스택이 하나 있다. 스택은 처음에 비어 있으며, 로봇은 명령 목록을 차례로 실행한다.

• 명령 a: 새 크리스털 펜던트를 하나 집어 스택의 맨 위에 올린다.
• 명령 1~9: 스택의 맨 위에서 그 숫자만큼 부품을 꺼내 새 고리에 차례로 매단 뒤(먼저 꺼낸, 즉 맨 위에 있던 부품을 가장 먼저 매단다), 완성한 고리를 스택의 맨 위에 올린다.

프로그램을 모두 실행하고 나면 스택에는 정확히 하나의 부품, 즉 완성된 샹들리에만 남는다. 펜던트 하나든, 아무리 복잡하게 조립한 고리든 스택에서는 한 개의 부품으로 센다.

어떤 프로그램은 어느 순간 스택에 부품을 너무 많이 쌓아 두어야 한다. 같은 디자인의 샹들리에를 조립하면서 필요한 스택 용량을 가장 작게 만들었을 때, 그 최소 용량을 구하라.

두 샹들리에는 모든 고리가 같은 부품을 같은 순서로 담고 있으면 같은 디자인이다. 고리는 원형이므로, 로봇이 고리를 만들 때 어떤 부품이 스택 맨 위에 오는지는 상관없고 부품들의 순환(cyclic) 순서만 중요하다(회전은 허용되지만 순서를 뒤집을 수는 없다). 예를 들어 스택 맨 위에 $\langle i_1, i_2, i_3, i_4 \rangle$가 (맨 위가 $i_1$) 놓인 상태에서 명령 4를 실행하면, $\langle i_2, i_3, i_4, i_1 \rangle$, $\langle i_3, i_4, i_1, i_2 \rangle$, $\langle i_4, i_1, i_2, i_3 \rangle$ 중 어떤 배치에서도 똑같은 고리가 만들어진다.

로봇을 위한 올바른 프로그램이 한 줄로 주어진다. 프로그램의 길이는 최대 $10\,000$자이며, 각 문자는 a 또는 숫자 1~9 중 하나다.

같은 디자인의 샹들리에를 조립하는 데 필요한 최소 스택 용량(동시에 스택에 담아야 하는 부품 개수의 최댓값)을 정수 하나로 출력한다.