Tokens

The police need a picture of what is being prepared before a public gathering takes place. Organizers now routinely announce their plans on web pages, so the decision was made to build a program that scans web pages and flags suspicious text automatically. The program reads English text and works out roughly what it says. That takes lexical analysis first, at the level of words and symbols, then syntactic analysis at the level of sentences. This problem covers the lexical part only.

A lexical analyzer reads the characters of a text in order and produces a sequence of tokens. Analyzing abc+123 under a grammar for arithmetic expressions produces the tokens abc, +, 123 in that order.

Look at the reading process more closely. After a, b and c have been read, the analyzer decides to build the token abc because the character that follows is +, and + cannot be part of an identifier. Here the moment the token is built is decided by a single character of the not yet read part of the text. After reading +, by contrast, the token can be built at once, because whatever comes next has no influence on it. Tokens therefore differ in how many characters of the not yet read part decide when they are built.

Web pages change often, and reanalyzing the whole text after every change is wasteful, so only the changed place and its surroundings are analyzed again. Because of the dependency above, a change to the text of one token can affect how several tokens before it are built. For each token $t$ we define $\mathrm{lookback}(t)$, the distance to the farthest token toward the start of the text whose construction is influenced by the text of token $t$. If there is no such token, $\mathrm{lookback}(t) = 0$. The distance between two tokens is the number of tokens lying between them plus one.

For abc+123 above, the three tokens have $\mathrm{lookback}$ values 0, 1 and 0.

Given a sequence of tokens, compute $\mathrm{lookback}$ for every token.

The first line contains the number of data sets $N$, with $N > 0$.

The data sets follow one after another. Each data set is one sequence of tokens, and each token is given on its own line by two integers $L$ and $A$. $L \ge 1$ is the number of characters of the token, and $A \ge 0$ is the number of characters of the not yet read part of the text that decide when the token is built. The sequence ends with a line 0 0, which does not describe a token. A data set with no tokens consists of the single line 0 0.

The length of the sequence and the total number of characters of the input text fit in a signed 32-bit integer and are otherwise unbounded. No token has a $\mathrm{lookback}$ value above 250000.

For each data set, first print the line Zadani X:, where $X$ is the number of the data set counted from one. Then print, for each token in input order, one line holding the $\mathrm{lookback}$ of that token.

Print one blank line between two consecutive data sets.