F 本初字符串

枚举

首先确定S的本初字符串T的长度有多少种情况，显然len(T) <= len(S)，枚举所有长度的话肯定超时，自己造几个样例，其实很容易发现规律，只需要枚举len(S)的所有因数。作为T长度就可以了，不想证明（其实是不会。。。）

由于要使T长度尽量小，所以肯定使从小到大枚举len(S)的所有因数。

贪心

长度与统计数贪心

对于每一个枚举的len(S)的所有因数L，拼接len(S)//L个T，就能和S一样长，枚举T的每一位T[j]，然后统计S对应同余位字母，选择出现次数最多的字母来作为T[j]，最后判断是否满足题意，超过半数字母相同。

字典序贪心

若当前L满足题意，T的每一位尽量选择字典序小的字母作为答案，因此对于T的每一位，从小到大枚举字母即可，然枚举后，还是能满足超过半数字母相同，则选择该字母。

T = int(input())
from collections import Counter
import string
while T:
    s = input().strip()
    
    # 获取len(S)的所有因数
    d = 1
    tmp = set()
    n = len(s)
    n_half = (n+1)//2
    while d*d <= n:
        if n % d == 0:
            tmp.add(d)
            tmp.add(n//d)
        d += 1
    
    # 从小到大，枚举T长度
    for L in sorted(tmp):
        # 同余位字母统计
        t = 0
        for start in range(L):
            cnt = Counter()
            i = start
            while i < n:
                cnt[s[i]] += 1
                i += L
            # 贪心，选最多的相同字母
            t += cnt.most_common()[0][1]
        
        # 贪心后超过半数相同，符合题意
        if t >= n_half:
#             print(L)
            # 开始贪心
            res = ''
            for start in range(L):
                cnt = Counter()
                i = start
                while i < n:
                    cnt[s[i]] += 1
                    i += L
                # 贪心，字典序小的字母开始选择
                # 当前位最多的字母数
                lt = cnt.most_common()[0][1]
                for w in string.ascii_lowercase:
                    # 选则当前字母还是能满足题意，那就优先选择
                    if t - lt + cnt[w] >= n_half:
                        res += w
                        # 更新t
                        t = t - lt + cnt[w]
                        break
            print(res)
            break
    T -= 1