Append

Consider the encoding scheme used by a well-known compression algorithm. We encode only sequences of lowercase letters. Such a sequence is encoded as a list of pairs $(p_i, r_i)$, where $p_i \ge 0$ is an integer and $r_i$ is either a single character (when $p_i = 0$) or an integer with $0 < r_i \le p_i$ (when $p_i > 0$).

Decoding processes the pairs in order and builds the output sequence:

• If $p_i = 0$, then $r_i$ is a character; append it to the end of the decoded sequence.
• If $p_i > 0$, then $r_i$ is an integer with $0 < r_i \le p_i$; append $r_i$ characters copied from the decoded sequence, starting $p_i$ positions before its current end.

For example, the pairs $(0, a), (1, 1), (0, b), (3, 3), (3, 3), (3, 2), (0, c)$ decode step by step: $(0, a)$ gives a; $(1, 1)$ gives aa; $(0, b)$ gives aab; $(3, 3)$ appends aab to give aabaab; the next $(3, 3)$ appends aab to give aabaabaab; $(3, 2)$ appends aa to give aabaabaabaa; and $(0, c)$ gives aabaabaabaac. Note that one string $w$ may have several different encodings.

For sequences $u$ and $v$, write $uv$ for their concatenation. Let $C_w$ denote an encoding of a lowercase-letter sequence $w$. Given an encoding $C_w$, count how many ways it can be split into two consecutive parts $C_w = C_u C_v$ such that:

• $C_u$ is the prefix consisting of the first few pairs and $C_v$ is the remaining suffix of pairs;
• $C_u$ is itself a valid encoding of some sequence $u$, and $C_v$ is itself a valid encoding of some sequence $v$;
• $w = uv$, and neither $u$ nor $v$ is empty.

Write a program that outputs this number.

The input consists of several blocks of lines. Each block describes one encoding $C_w$. A line of a block contains either two integers $p_i$ and $r_i$ (with $r_i \le p_i < 1000$) separated by a single space, or the integer $0$ followed by a single space and a single lowercase letter. Each block is terminated by one empty line. The input may contain several such blocks, one after another.

For each block, print a single line containing the number of ways the encoding $C_w$ can be written as $C_u C_v$ with $w = uv$, where both $u$ and $v$ are non-empty and each part is a valid encoding on its own.