字符串

内存限制：256 MiB 时间限制：10 Sec

提交提交记录讨论

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

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

有多组数据。

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

每组数据第一行一个整数n，第二行一个长度为n的字符串。

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

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

样例输入


			1

11

abcabacbcac

样例输出