



test cases:
4
2
aa
6
aabaab
6
aababc
278
lfpbavjsmppdtlkfwnyfmbdhptdswsoulrbhyjhpmpscfliuqnynejgnxolzbdoztclzbozqomvioszkulekcvcoqoymonrqgrjdtktsqtinmdcvservaxcbirnpfungsgkiftchwlmtbzqgaraovjknsgiegkvdbolmeunvrxrpscnfprodujeqtidwtoijgqtygovjknssmabwlhqjfvgwrdhaazejsfgilnpmmhkefndzvyonwpkzwwpdpbrudqmwmjschwnnjyoepxophc
expected output:
0
2
2
133