사이클 수 세기

ICPC라는 이름의 작은 폰 노이만 구조 컴퓨터는 16비트 정수 기계입니다. 명령어 메모리는 충분히 많지만 데이터 메모리는 M이라고 부르는 칸 하나뿐입니다. ICPC에는 R1, R2, R3, R4, R5, PC까지 여섯 개의 레지스터가 있습니다. R1부터 R5까지는 범용 레지스터이고, PC는 다음에 실행할 명령어의 주소를 담는 프로그램 카운터로, 제어 흐름 명령어로만 값을 바꿀 수 있습니다.

이 기계는 일반적인 인출, 해독, 실행 주기를 따릅니다. PC는 제어 흐름 명령어를 제외하면 보통 자동으로 증가합니다. ICPC의 주소 지정 방식은 즉치값과 레지스터 두 가지뿐이며, PC는 절대 피연산자로 쓸 수 없습니다. 전체 명령어 집합은 아래와 같으며, 여기서 r은 레지스터, v는 레지스터 또는 정수값, M은 데이터 메모리 칸입니다.

ICPC 명령어	C로 표현한 의미
`load r`	`r = M;`
`store v`	`M = v;`
`move r v`	`r = v;`
`add r v`	`r += v;`
`sub r v`	`r -= v;`
`loop r ... pool`	`while (r > 0) { ... }`
`cond r ... dnoc`	`if (r > 0) { ... }`

loop는 pool로 닫히고 cond는 dnoc로 닫힙니다. 그 사이에 놓인 명령어들이 조건이 참인 동안 실행되는 명령어입니다.

인출-해독-실행 주기의 각 단계를 한 주기(cycle)라고 부릅니다. 따라서 명령어 하나는 최소 세 주기가 걸리며, dnoc을 제외한 모든 명령어는 정확히 세 주기가 걸립니다. dnoc은 cond의 끝을 나타낼 뿐 실제로 실행되지 않는, ICPC의 유일한 의사 명령어입니다. pool은 dnoc처럼 loop의 끝을 표시하지만, 반복의 끝에서 제어가 반복문의 처음으로 돌아가야 하므로 실제로 실행됩니다.

실행 시간을 줄이기 위해 ICPC는 파이프라이닝을 사용합니다. 세 명령어 A, B, C가 차례로 실행된다고 합시다. A의 해독 단계는 B의 인출 단계와 겹칠 수 있고, A의 실행 단계는 B의 해독 단계 및 C의 인출 단계와 겹칠 수 있습니다. 그래서 move 하나와 add 하나를 이어서 실행하면 6주기가 아니라 4주기만 걸립니다. 그림 1(a)의 처음 두 명령어가 이를 보여줍니다. 그림에서 F는 인출, D는 해독, E는 실행을 뜻합니다.

PC가 제어 흐름 명령어에 도달하면 파이프라이닝이 멈춥니다. 그 명령어를 실행하기 전에는 다음 명령어가 무엇인지 알 수 없기 때문입니다. 그림 1(a)의 cond가 이를 보여줍니다. dnoc은 실행되지 않으며, 그림 1(a) 전체는 9주기가 걸립니다.

pool 역시 제어 흐름 명령어입니다. 그림 1(b)에서는 loop뿐 아니라 pool도 파이프라이닝을 멈추게 합니다.

그림 1: 예시 프로그램과 그에 해당하는 주기 수.

첫 줄에는 테스트 케이스의 수 T가 주어집니다. 각 테스트 케이스는 명령어 줄의 수 L(L > 0)이 적힌 줄로 시작하고, 그 뒤에 명령어가 한 줄에 하나씩 L줄에 걸쳐 주어집니다.

줄은 제어 구조의 중첩에 따라 들여쓰기가 되어 있을 수 있습니다. 모든 loop와 cond는 적어도 하나의 명령어를 포함하므로 빈 반복문이나 빈 분기는 없습니다. 각 입력 줄은 최대 100자입니다. 즉치값은 16비트 2의 보수 정수로, $-32768 \le N \le 32767$ 범위입니다. 연산 부호와 피연산자는 적어도 하나의 공백으로 구분됩니다. 무한 반복이 있는 테스트 케이스는 없습니다.

사이클 수 세기

문제

입력

출력