对于一个字符串s[1..n]，它的前缀定义为子串s[1..i]（i<=n），它的后缀定义为s[j..n]（1<=j），现在给定一个字符串，任取它的不相交的一对前缀和后缀（前后缀可以为空，但不能同时为空），并拼成一个新串（前缀+后缀），请问有多少种不同的拼法？

输入数据第一行为一个正整数T(1<=T<=30)，表示测试数据的组数。

接下来是T组测试数据， 每组数据第一行，包括一个正整数n(2<=n<=2000)，代表字符串的长度，第二行输入字符串，字符串仅包含小写字母。

对于每一组输入数据， 输出一行”Case #id: ans”， 表示第id组数据结果， id从1开始， ans表示方案数，详细情况可以参见样例。