D-卡拉巴什的字符串_2020 CCPC Wannafly Winter Camp Day2 Div.1&2（重现赛）

时间限制：C/C++/Rust/Pascal 4秒，其他语言8秒
空间限制：C/C++/Rust/Pascal 512 M，其他语言1024 M
64bit IO Format: %lld

题目描述

卡拉巴什是字符串大师，这天他闲着无聊，又造了个字符串问题。
给定一个长度为 ${N}$ 字符串 ${S}$ ，定义后缀 ${i}$ 为从第 ${i}$ 个位置开始的后缀，即 $s_{i}s_{i+1}...s_{n}$ ，定义 ${lcp(i,j)}$ 为后缀 ${i}$ 和后缀 ${j}$ 的最长公共前缀。
卡拉巴什想要知道，每次他给出一组 ${i}$ ， ${j}$ ，你能否快速告诉他 ${lcp(i,j)}$ 。
卡拉巴什的好朋友葫芦是字符串宗师，他认为这个题太无聊，于是他想了另一个问题，假设有一个集合 $\{lcp(i,j) | 1\leq i < j\leq N\}$ ，他想知道这个集合的 ${MEX}$ 值是多少。一个集合的 ${MEX}$ 值为最小的没有出现在集合中的非负整数。
这个问题对卡拉巴什来说太容易了，于是葫芦想知道，对于字符串的每一个前缀，对应的集合的 ${MEX}$ 值是多少。

输入描述:

第一行一个整数 ，表示数据组数。
对于每组数据，共一行，表示字符串 。
输入数据保证所有字符串长度和不超过 。保证字符串只包含小写字母。

输出描述:

对于每组数据，输出个整数，表示每一个前缀对应的  值。

示例1

输入

复制

2
ababa
baa

输出

复制

0 1 2 3 4
0 1 2