Special String:

Consider the string of infinite length obtained by repeating abcdefghijklmnopqrstuvwxyz infinitely many times. That is, it looks like abc...xyzabc...xyzabc...

Let string B$B$ be the prefix of this string of length M$M$. For example,

• if M=6$M=6$, B=$B=$ abcdef
• if M=29$M=29$, B=$B=$ abcdefghijklmnopqrstuvwxyzabc

Vedansh calls a string X$X$ special if it contains B$B$ as a substring. Formally, X$X$ is special if for some 1≤L≤R≤|X|$1\le L\le R\le |X|$, XL…R=B$X_{L\dots R}=B$.

Vedansh has string S$S$ of length N$N$ (consisting of lowercase Latin letters only). He wants to convert S$S$ into a special string. To do so he can perform the following operation:

• Pick an i$i$ such that 1≤i≤N$1\le i\le N$ and delete Si$S_i$. The remaining parts of S$S$ are concatenated.

Since Vedansh is lazy, he wants to do this in the minimum number of operations or determine if S$S$ cannot be converted to a special string. Help Vedansh in doing so.

Input Format

• The first line of input contains a single integer T$T$ — the number of test cases. The description of T$T$ test cases follows.
• Each test case consists of three lines of input
  • The first line of each test case contains an integer N$N$ — the length of the string S$S$.
  • The second line of each test case contains the string S$S$ which consists of lowercase Latin letters only.
  • The third line of each test case contains an integer M$M$ — the length of the string B$B$ whose form is described in the statement.

Output Format

For each test case, if A$A$ can be converted to a special string, output the minimum number of operations to do so. Otherwise output −1$-1$.

Constraints

• 1≤T≤1000$1\le T\le 1000$
• 1≤M≤N≤106$1\le M\le N\le {10}^6$
• S$S$ consists of only lowercase Latin letters
• It is guaranteed that the sum of N$N$ over all test case does not exceed 106${10}^6$.

Sample Input 1 

3
9
ababbdced
4
7
bdcgehx
5
6
acbcbd
3

Sample Output 1 

3
-1
1

Explanation

Test case 1$1$: M=4$M=4$, so B=abcd$B=abcd$. We can delete the following characters from S$S$: ababbdced$ababbdced$ →$\to$ ababcd–––––$ab\underset{\_}{abcd}$, which has B$B$ as a substring.

Test case 2$2$: M=5$M=5$, so B=abcde$B=abcde$. It can be shown that S$S$ can not be converted into a special string.

Test case 3$3$: M=3$M=3$, so B=abc$B=abc$. We can delete the following characters from S$S$: acbcbd$acbcbd$ →$\to$ abc–––bd$\underset{\_}{abc}bd$, which has B$B$ as a substring.

SOLUTION:

#include<bits/stdc++.h>

using namespace std;

#define fi first

#define se second

#define mp make_pair

#define pb push_back

#define pf push_front

#define LC k<<1

#define RC k<<1|1

#define IO cin.sync_with_stdio(false); cin.tie(0); cout.tie(0);

#define all(x) (x).begin(), (x).end()

#define SZ(x) ((int)(x).size())

#define rep(i,a,n) for (int i = a; i < n; i++)

#define repn(i,a,n) for (int i = a; i <= n; i++)

#define per(i,a,n) for (int i = n - 1; i >= a; i--)

#define pern(i,a,n) for (int i = n; i >= a; i--)

typedef long long LL;

typedef unsigned long long ull;

typedef pair<int, int> PII;

typedef pair<double, double> PDD;

const int N = 1100000;

const int M = 1100000;

const int mod = 1e9+7;

const int inf = (int)1e9;

const double eps = 1e-9;

int T, n, m;

string s;

int nxt[N][26];

int f[N][18];

int pp[110], ans;

int main()

{

IO;

cin >> T;

while (T--) {

cin >> n;

cin >> s;

cin >> m;

memset(pp, 0, sizeof(pp));

rep(i, 0, 26) pp[i] = n, nxt[n][i] = n, nxt[n + 1][i] = n;

rep(i, 0, 18) f[n][i] = n, f[n + 1][i] = n;

per(i, 0, n) {

pp[s[i] - 'a'] = i;

rep(j, 0, 26) nxt[i][j] = pp[j];

int now = i;

rep(j, 0, 26) now = nxt[now][j];

f[i][0] = now;

rep(j, 1, 18) {

f[i][j] = f[f[i][j - 1] + 1][j - 1];

}

}

ans = inf;

int rnd = m / 26, rem = m % 26;

rep(i, 0, n) {

int now = i;

per(j, 0, 18) if (rnd >> j & 1) now = f[now][j] + 1;

rep(j, 0, rem) now = nxt[now][j];

if (rem == 0) now--;

if (now < n) ans = min(ans, (now - i + 1) - m);

}

if (ans == inf) ans = -1;

cout << ans << "\n";

}

return 0;

}