#P5439. [2018年福建冬令营]字符串

    ID: 4451 传统题 3000ms 256MiB 尝试: 335 已通过: 69 难度: 7 上传者: 标签>CF2200提高+/省选-有限候选集缩减暴力枚举回溯搜索贪心保持领先

[2018年福建冬令营]字符串

Description

对于字符串s,若它的长度为n,最小循环节长度为m,那么我们定义它的价值为n^2/m。

给定一个只包含a,b,c的字符串,求它的价值最大的非空子序列的价值。 有多组数据。

Format

Input

第一行一个整数t表示数据组数。

每组数据第一行一个整数n

第二行一个长度为n的字符串。

t<=10,1<=n<=10^5

Output

每组数据输出一行一个整数表示答案。

Samples

1
11
abcabacbcac
18