String Theory

Acesrc는 난징 대학의 유명한 문자열 이론가로, 그를 따를 사람이 없다. 그는 중요한 말은 항상 $k$번 말해야 한다고 주장한다. 또한 어떤 비어 있지 않은 문자열 $k$개를 이어 붙여 얻을 수 있는 문자열은 모두 splendid하다고 믿는다. 그래서 그는 항상 신입생들에게 이렇게 가르친다. "String theory problems are important! String theory problems are important! ... String theory problems are important!"

오늘 그는 신입생들이 자신의 가르침을 기억하는지 확인하려 한다. 소문자로 이루어진 문자열 하나를 제시하고, 그 문자열의 splendid한 부분 문자열 개수를 묻는다. 아무도 이 문제를 풀지 못하고, 그들은 몇 시간 동안 혼날 것이다. 당신이 그들을 도와줄 수 있는가?

서로 다른 위치에서 나타난 같은 splendid 부분 문자열은 각각 따로 세야 한다.

첫 줄에는 테스트 케이스의 개수를 나타내는 정수 $T$ $(1 \leq T \leq 10)$가 주어진다. 각 테스트 케이스의 첫 줄에는 정수 $k$ $(1 \leq k \leq 20)$가 주어진다. 테스트 케이스의 둘째 줄에는 소문자로만 이루어진 문자열 $S$가 주어지며, 길이는 $1$ 이상 $3 \times 10^5$ 이하다. 모든 테스트 케이스에서 문자열 길이의 합은 $10^6$을 넘지 않는다.

각 테스트 케이스마다 답을 한 줄에 하나의 정수로 출력한다.