SP34020 ADAPET - Ada and Pet

Ada the Ladybug 刚给自己买了一只新宠物。她正在考虑一个名字。她已经想到了一个美丽的名字，但现在她并不认为这个名字“足够好”。她想找到一个新名称，它将包含原始名称至少 $K$ 次作为子字符串（以强调其重要性）。由于 ada 不希望宠物的名字太长，她想找到最短的一个 - 你能找到它的长度吗？

第一行输入将包含 $T$，即测试用例的数量。 接下来T行每行将包含一个非空字符串s，由小写英文字母和一个数字组成（给定名称在新名称中的次数）。 所有测试用例的字符串长度总和不会超过 $5 * 10 ^ {5} $

对于每个测试用例打印新名称的最小长度。