给定一个字符串 $s$，我们可以得到该字符串的所有非空前缀。
例如，当 $s$ 为 abab 时，其前缀为 a、ab、aba、abab。
对于每个前缀，我们可以计算它在 $s$ 中匹配的次数。
例如，在 abab 中，a 匹配两次，ab 匹配两次，aba 匹配一次，abab 匹配一次。
现在，对于给定的字符串 $s$，请你计算其所有前缀的匹配次数之和。
例如，对于 abab，这个值为 2+2+1+1=6。
由于答案可能很大，因此输出对 10007 取模后的结果。

第一行包含整数 $T\ (1 \leq T \leq 100)$，表示共有 $T$ 组测试数据。
每组数据第一行包含整数 $n\ (1 \leq n \leq 2\times 10^5)$，表示字符串 $s$ 的长度。
第二行包含字符串 $s$，保证 $s$ 仅由小写字母构成。

每组数据输出一行，一个整数，表示对 10007 取模后的结果。