第一题

描述

核心子串是指包含所有小写字母的字符串，现在给出一个仅包含小写字母的字符串，请找出其中最短的核心子串。

输入

在第一行给出一个正整数 T，代表测试数据的组数

每组输入在一行中给出一个仅包含小写字母的字符串 $S_i$

1≤T≤15

$|S_i|<=10^6$

输出

每组输入在一行中输出最短的核心子串，若不唯一，输出最先出现的那个

若不存在核心子串，输出 「not found」

第二题

描述

给定一个环形数组，保证数组元素之和为零，现在允许将数组进行切割，求最多分成多少个总和为零的片段。

输入

输入第一行给出一个正整数 T，代表测试数据的组数

每组数据在第一行给出一个正整数 n，然后在第二行给出 n 个整数 $a[i]$

1≤T≤200

1≤n≤10^4

$|a_i|≤10000$

输出

对于每组输入在一行中输出一个正整数，代表最多片段的个数

急