# Alice's Classified Message

Time Limit: 16000/8000 MS (Java/Others)

Memory Limit: 131072/131072 K (Java/Others)

## Description

Alice wants to send a classified message to Bob. She tries to encrypt the message with her original encryption method. The message is a string $S$, which consists of $N$ lowercase letters.

$S[a…b]$ means a substring of S ranging from $S[a]$ to $S[b]$ ($0≤a≤b<N$). If the first $i$ letters have been encrypted, Alice will try to find a magic string $P$. Assuming $P$ has $K$ letters, $P$ is the longest string which satisfies $P=S[T...T+K-1]$ ($0≤T<i$，$T+K≤N$) and $P=S[i…i+K-1] (i+K≤N)$. In other words, $P$ is a substring of $S$, of which starting address is within $[0...i-1]$, and $P$ is also a prefix of $S[i...N-1]$. If $P$ exists, Alice will append integer $K$ and $T$ to ciphertext. If $T$ is not unique, Alice would select the minimal one. And then $i$ is incremented by $K$. If $P$ does not exist, Alice will append -1 and the ASCII code of letter $S[i]$ to ciphertext, and then increment $i$ by 1.

Obviously the first letter cannot be encrypted. That is to say, $P$ does not exist when $i=0$. So the first integer of ciphertext must be -1, and the second integer is the ASCII code of $S[0]$.

When $i=N$, all letters are encrypted, and Alice gets the final ciphertext, which consists of many pairs of integers. Please help Alice to implement this method.

## Input

The first line of input contains an integer $T$, which represents the number of test cases ($T≤50$). Each test case contains a line of string, which has no more than 100000 lowercase letters. It is guaranteed that the total length of the strings is not greater than $2×10^6$.

## Output

For each test case, output a single line consisting of “Case #X:” first. $X$ is the test case number starting from 1. Output the ciphertext in the following lines. Each line contains two integers separated by a single space.

## Sample Input

2
aaaaaa
aaaaabbbbbaaabbc

## Sample Output

Case #1:
-1 97
5 0
Case #2:
-1 97
4 0
-1 98
4 5
5 2
-1 99

wange2014

## Source

2015ACM/ICPC亚洲区合肥站-重现赛（感谢中科大）