% Source:
% 	MIPT 2015. Day 03, problem G 
% 	https://contest.yandex.ru/admin/contest-submissions?contestId=1867

\begin{problem}{LZSS encoding}
{lzss.in}{lzss.out}
{1 sec}{256 mb}{}

Алиса хочет отправить сообщение Бобу.
Она хочет зашифровать сообщение, используя оригинальный метод шифрования.
Сообщение -- строка $S$, состоящая из $N$ строчных английских букв.

$S[a\dots b]$ означает подстроку $S$ от $S[a]$ до $S[b]$ ($0 \le a \le b < N$). 
Если первые $i$ букв уже зашифрованы, Алиса найдёт такие $(j, k) \colon s[j..j+k] = s[i..i+k], k \ge 0, 0 \le j < i, k = \max$.
Если несколько $j$ дают максимальное $k$, Алиса выберет минимальное $j$.
Если $k > 0$ Алиса добавит пару $\langle k, j \rangle$ в шифр и увеличит $i$ на $k$, иначе
Алиса добавит -1 и ASCII код буквы $S[i]$ в шифр и увеличит $i$ на $1$.

Очевидно шифр начнёт с -1, далее будет ASCII код символа $S[0]$.
Помогите Алисе реализовать её метод шифрования.

\InputFile

Перрвая строка ввода содержит количество тестов $T$ ($1 \le T \le 50$). 
Следующие $T$ строк содержат сообщения для шифровки, каждое длины от $1$ до $10^5$, состоящие из строчных английских букв. 
Гарантируется, что суммарная длина всех сообщений не превосходит $2 \cdot 10^6$.

\OutputFile

Для каждого теста на отдельной строке выведите ``\t{Case \#{}X:}'', где $X$ -- номер теста, нумерация с $1$. 
Далее выведите шифр, в каждой строке по два целых числа через пробел.

\Examples

\begin{example}
\exmp{
2
aaaaaa
aaaaabbbbbaaabbc
}{
Case \#{}1:
-1 97
5 0
Case \#{}2:
-1 97
4 0
-1 98
4 5
5 2
-1 99
}%
\end{example}

\end{problem}
