토큰

경찰은 공개 집회가 열리기 전에 무엇이 준비되고 있는지 미리 파악해야 한다. 집회를 여는 쪽이 웹 페이지에 계획을 올리는 일이 흔해지면서, 웹 페이지를 훑어 수상한 텍스트를 자동으로 찾아내는 프로그램을 만들기로 했다. 이 프로그램은 영어 텍스트를 읽어 내용을 대략 파악한다. 그러려면 먼저 단어와 기호 수준에서 어휘 분석을 하고, 그 다음 문장 수준에서 구문 분석을 한다. 이 문제에서는 어휘 분석만 다룬다.

어휘 분석기는 텍스트의 문자를 차례로 읽으면서 토큰의 열을 만든다. 산술식 문법으로 abc+123을 분석하면 토큰 abc, +, 123이 차례로 만들어진다.

문자를 읽는 과정을 더 자세히 보자. a, b, c를 읽은 다음 토큰 abc를 만들기로 결정하는 근거는 그 뒤에 오는 문자가 +라는 사실이다. +는 식별자의 일부가 될 수 없기 때문이다. 이 경우 토큰을 만드는 시점을 결정하는 것은 아직 읽지 않은 부분의 첫 문자 하나다. 반면 +를 읽은 직후에는 뒤에 무슨 문자가 오든 토큰 생성에 영향을 주지 않으므로 곧바로 토큰을 만들 수 있다. 이렇게 토큰마다 아직 읽지 않은 부분의 문자 몇 개가 생성 시점을 결정하는지가 다르다.

웹 페이지는 자주 바뀌고, 바뀔 때마다 텍스트 전체를 다시 분석하는 것은 낭비다. 그래서 바뀐 자리와 그 주변만 다시 분석한다. 그런데 위와 같은 의존 관계 때문에 어떤 토큰의 텍스트가 바뀌면 그보다 앞에 있는 토큰 몇 개의 생성까지 영향을 받는다. 그래서 각 토큰 $t$에 대해 $\mathrm{lookback}(t)$를 정의한다. 이 값은 토큰 $t$의 텍스트에 생성이 영향받는 토큰 가운데 텍스트의 시작 쪽으로 가장 멀리 있는 토큰까지의 거리다. 그런 토큰이 없으면 $\mathrm{lookback}(t) = 0$이다. 두 토큰 사이의 거리는 둘 사이에 놓인 토큰의 개수에 1을 더한 값이다.

위의 abc+123에서 세 토큰의 $\mathrm{lookback}$은 차례로 0, 1, 0이다.

토큰 열이 주어질 때 모든 토큰의 $\mathrm{lookback}$을 구하는 프로그램을 작성하시오.

첫째 줄에 데이터 세트의 개수 $N$이 주어진다. $N > 0$이다.

이어서 데이터 세트가 차례로 주어진다. 각 데이터 세트는 토큰 열 하나이며, 토큰 하나가 한 줄에 두 정수 $L$, $A$로 주어진다. $L \ge 1$은 그 토큰의 문자 개수이고, $A \ge 0$은 아직 읽지 않은 부분의 문자 가운데 그 토큰을 만드는 시점을 결정하는 문자의 개수다. 토큰 열은 0 0 줄로 끝나며, 이 줄은 토큰을 나타내지 않는다. 토큰이 하나도 없는 데이터 세트는 0 0 줄 하나로만 이루어진다.

토큰 열의 길이와 입력 텍스트의 전체 문자 수는 부호 있는 32비트 정수 범위 안에 들어가고, 그 밖의 제한은 없다. 어떤 토큰에서도 $\mathrm{lookback}$ 값은 250000을 넘지 않는다.

각 데이터 세트마다 먼저 Zadani X: 한 줄을 출력한다. $X$는 데이터 세트의 번호이고 1부터 센다. 그 다음 입력에 주어진 순서대로 토큰마다 한 줄에 그 토큰의 $\mathrm{lookback}$을 출력한다.

이어지는 두 데이터 세트 사이에는 빈 줄을 하나 출력한다.