이번 문제에서 크기가 k인 알파벳이란, 아래와 같은 리스트에서 처음 k개의 글자를 말한다.

a, b, c, ... , z, A, B, C, ... , Z, 0, 1, ... , 9.

각각의 테스트 케이스마다 k가 주어지며, 크기가 k인 알파벳만 고려한다.

문자열 t[1..m]이 문자열 s[1..n]의 부분 수열이 되려면, t[1] = s[i₁], t[2] = s[i₂], ..., t[m] = t[i_m]을 만족하는 인덱스 1 ≤ i₁ < i₂ <... i_m ≤ n가 존재해야 한다. 예를 들어, acb는 babcaab의 부분 수열이다.

문자열 s[1..n]이 주어졌을 때, s의 부분 수열이 아닌 문자열 t[1..m] 중에서 m 값이 가장 작은 것을 찾고, 그러한 문자열의 개수를 구하는 프로그램을 작성하시오.

입력 형식

첫째 줄에 테스트 케이스의 개수 t ≤ 100이 주어진다. 각각의 테스트 케이스는 알파벳의 크기 k (k ∈ [1, 62])와 문자열 s[1..n] (n ∈ [1, 10⁶])이 주어진다.

출력 형식

각각의 테스트 케이스마다, 두 개의 정수를 출력한다. 첫 번째 정수는 가장 작은 m이고, 두 번째 정수는 가능한 문자열 t[1..m]의 개수를 10⁹ + 7로 나눈 나머지이다.

예제 입력

3
2 abba
62 0123456789
3 aabbcbbcbabcbab

예제 출력

3 5
1 52
4 7