import static java.lang.Math.*; import static java.util.Arrays.*; import java.io.*; import java.lang.reflect.*; import java.util.*; import java.util.concurrent.*; import java.util.function.*; public final class Main{ public static void main(String[] args) throws Exception{ MyReader in = new MyReader(System.in); MyWriter out = new MyWriter(System.out,false),log = new MyWriter(System.err,true); int T = Solver.multi ? in.it() : 1; while (T-- > 0) Optional.ofNullable(new Solver(in,out,log).solve()).ifPresent(out::println); out.flush(); } } class Solver extends BaseSolver{ public Solver(MyReader in,MyWriter out,MyWriter log){ super(in,out,log); } public static boolean multi = true; public Object solve(){ int N = in.it(); int M = in.it(); String S = in.str(); int c1 = calc(S); if (M <= c1) return 1; int c2 = calc(S +S); long a = c2 -c1; long b = c1 -a; if (a == 0) return -1; return ceil(M -b,a); } private int calc(String s){ var rh = new RollingHash(s.toCharArray(),false); int ret = 1; for (int i = 0;i < s.length();i++) { int l = (ret -1) /2; while (0 <= i -(l +1) && i +l +2 <= s.length() && rh.get(i -(l +1),i) == rh.get(i +l +2,i +1)) l++; ret = max(ret,l *2 +1); l = ret /2; while (0 <= i -l && i +l +2 <= s.length() && rh.get(i -l,i +1) == rh.get(i +l +2,i +1)) l++; ret = max(ret,l *2); } return ret; } int[][] trans(int[]... T){ return Util.arr(new int[T[0].length][],i -> Util.arrI(T.length,j -> T[j][i])); } // void add(SegmentTree seg,int a,long[] map){ seg.upd(a,map[a]); } // // void rem(SegmentTree seg,int a,long[] map){ seg.upd(a,-map[a]); } // // long[] mo(int N,int[] A,int[][] T,long[] map,SegmentTree seg,long[] ans){ // int k = 32 -Integer.numberOfLeadingZeros((int) (Math.sqrt(1.5 /T.length) *N) +1); // sort(T,(a,b) -> (a[0] >>k != b[0] >>k ? a[0] -b[0] : (a[0] >>k &1) == 1 ? a[1] -b[1] : b[1] -a[1])); // int l = T[0][0]; // int r = l -1; // for (var t:T) { // while (t[0] < l) // add(seg,A[--l],map); // while (r < t[1]) // add(seg,A[++r],map); // while (l < t[0]) // rem(seg,A[l++],map); // while (t[1] < r) // rem(seg,A[r--],map); // ans[t[2]] = seg.get(0,100_000 +1).v; // } // return ans; // } } class RollingHash{ private static long MOD = (1L <<61) -1,MASK30 = (1L <<30) -1,MASK31 = (1L <<31) -1, base = ThreadLocalRandom.current().nextLong(Util.infI,MOD); private static long[] pow = {1}; int n; private long[] hash,S; private boolean updatable; private RollingHash rev; public RollingHash(char[] S,boolean updatable){ this(Util.arrL(S.length,i -> S[i]),updatable); } public RollingHash(int[] S,boolean updatable){ this(Util.arrL(S.length,i -> S[i]),updatable); } public RollingHash(long[] S,boolean updatable){ this.S = new long[n = S.length]; this.updatable = updatable; hash = new long[n +1]; if (pow.length <= n) { int s = pow.length; pow = copyOf(pow,max(pow.length <<1,n +1)); for (int i = s;i < pow.length;i++) pow[i] = mul(pow[i -1],base); } for (int i = 0;i < n;i++) set(i,S[i]); } public long get(int i){ return get(i,i +1); } public long get(int l,int r){ if (l > r) return (rev == null ? rev = rev() : rev).get(n -l,n -r); return mod(hash(r) -mul(hash(l),pow[r -l])); } public void upd(int i,long v){ assert updatable; set(i,v); if (rev != null) rev.set(n -i -1,v); } private void set(int i,long v){ if (updatable) for (int x = i +1;x <= n;x += x &-x) hash[x] = mod(hash[x] +mul(v -S[i],pow[x -i -1])); else hash[i +1] = mod(mul(hash[i],base) +v); S[i] = v; } private long hash(int i){ long ret = 0; if (updatable) for (int x = i;x > 0;x -= x &-x) ret = mod(ret +mul(hash[x],pow[i -x])); else ret = hash[i]; return ret; } private RollingHash rev(){ long[] s = new long[n]; for (int i = 0;i < n;i++) s[i] = S[n -1 -i]; return new RollingHash(s,updatable); } private static long mul(long a,long b){ long au = a >>31; long ad = a &MASK31; long bu = b >>31; long bd = b &MASK31; long mid = ad *bu +au *bd; return mod((au *bu <<1) +(mid >>30) +((mid &MASK30) <<31) +ad *bd); } private static long mod(long val){ return val < 0 ? val +MOD : (val = (val &MOD) +(val >>61)) < MOD ? val : val -MOD; } } class Matrix{ public static long[] mul(long[] a,long[][] b){ assert a.length == b.length; int H = b[0].length,W = a.length; long[] ret = new long[H]; for (int i = 0;i < H;i++) for (int j = 0;j < W;j++) ret[i] = (ret[i] +a[j] *b[j][i]) %Util.mod; return ret; } public static long[][] mul(long[][] a,long[][] b){ assert a[0].length == b.length; int H = a.length,W = b[0].length,Z = b.length; long[][] ret = new long[H][W]; for (int z = 0;z < Z;z++) for (int i = 0;i < H;i++) for (int j = 0;j < W;j++) ret[i][j] = (ret[i][j] +a[i][z] *b[z][j]) %Util.mod; return ret; } public static long[][] pow(long[][] x,long n){ long[][] ret = new long[x.length][x.length]; for (int i = 0;i < x.length;i++) ret[i][i] = 1; for (;0 < n;x = (n >>= 1) > 0 ? mul(x,x) : x) if ((n &1) == 1) ret = mul(ret,x); return ret; } } class Grid{ private int[][] dirs = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}}; private int H,W; public Grid(int H,int W){ this.H = H; this.W = W; } public int[] sur(int p){ MyList tmp = sur(toi(p),toj(p)); int[] ret = new int[tmp.size()]; for (int i = 0;i < tmp.size();i++) ret[i] = top(tmp.get(i)[0],tmp.get(i)[1]); return ret; } public MyList sur(int i,int j){ MyList ret = new MyList<>(); for (var d:dirs) { int ni = i +d[0]; int nj = j +d[1]; if (valid(ni,H) && valid(nj,W)) ret.add(new int[]{ni, nj}); } return ret; } private boolean valid(int i,int N){ return 0 <= i && i < N; } public int top(int i,int j){ return i *W +j; } public int toi(int p){ return p /W; } public int toj(int p){ return p %W; } } class PrefixSum{ private long[] sum; private int i; public PrefixSum(int n){ sum = new long[n +1]; } public PrefixSum(long[] a){ this(a.length); for (int i = 0;i < a.length;i++) sum[i +1] = sum[i] +a[i]; } public void add(long a){ sum[i +1] = sum[i++] +a; } public long get(int l,int r){ return sum[r] -sum[l]; } public long get(int i){ return get(i,i +1); } } class Edge { public int id,u,v; public L val; public Edge re; public Edge(int id,int u,int v,L val){ this.id = id; this.u = u; this.v = v; this.val = val; } } class Graph { public int n; public MyList> es; private MyList>[] go,bk; public Graph(int n,boolean dir){ this.n = n; go = Util.cast(new MyList[n]); bk = dir ? Util.cast(new MyList[n]) : go; for (int i = 0;i < n;i++) { go[i] = new MyList<>(); bk[i] = new MyList<>(); } es = new MyList<>(); } protected L inv(L l){ return l; } public void addEdge(int u,int v){ addEdge(u,v,null); } public void addEdge(int u,int v,L l){ var e = new Edge<>(es.size(),u,v,l); var re = new Edge<>(e.id,e.v,e.u,inv(e.val)); es.add(e); go[u].add(re.re = e); bk[v].add(e.re = re); } public MyList> go(int u){ return go[u]; } public MyList> bk(int u){ return bk[u]; } } class UnionFind{ int num; protected int[] dat; protected int[] nxt; public UnionFind(int n){ dat = new int[n]; nxt = new int[n]; setAll(nxt,i -> i); fill(dat,-1); num = n; } public int root(int x){ return dat[x] < 0 ? x : (dat[x] = root(dat[x])); } public boolean same(int u,int v){ return root(u) == root(v); } public boolean unite(int u,int v){ if ((u = root(u)) == (v = root(v))) return false; if (dat[u] > dat[v]) { u ^= v; v ^= u; u ^= v; } dat[u] += dat[v]; dat[v] = u; num--; nxt[u] ^= nxt[v]; nxt[v] ^= nxt[u]; nxt[u] ^= nxt[v]; return true; } public int size(int x){ return -dat[root(x)]; } public int[] getGroup(int x){ int[] ret = new int[size(x)]; for (int i = 0,c = root(x);i < ret.length;i++) ret[i] = c = nxt[c]; return ret; } } class MySet implements Iterable{ private Set set; private BitSet bit; public MySet(){ set = new HashSet<>(); } public int size(){ return set != null ? set.size() : bit.cardinality(); } public void add(int x){ if (set != null) { set.add(x); if (set.size() == 100) { bit = new BitSet(); for (int i:set) bit.set(i); set = null; } } else bit.set(x); } public boolean contains(int x){ return set == null ? bit.get(x) : set.contains(x); } @Override public Iterator iterator(){ return set != null ? set.iterator() : new Iterator<>(){ int w = bit.nextSetBit(0); @Override public Integer next(){ int ret = w; w = bit.nextSetBit(w +1); return ret; } @Override public boolean hasNext(){ return w != -1; } }; } } class Data extends BaseV{ long v; public Data(long v){ this.v = v; } @Override public String toString(){ return v +""; } } abstract class Sum3D{ private long[] sum; private int w,d; public Sum3D(int h,int w,int d){ this.w = w; this.d = d; sum = new long[(h +1) *(w +1) *(d +1)]; for (int i = 0;i < h;i++) for (int j = 0;j < w;j++) for (int k = 0;k < d;k++) sum[top(i +1,j +1,k +1)] = a(i,j,k) +sum[top(i,j +1,k +1)] +sum[top(i +1,j,k +1)] +sum[top(i +1,j +1,k)] -sum[top(i +1,j,k)] -sum[top(i,j +1,k)] -sum[top(i,j,k +1)] +sum[top(i,j,k)]; } abstract long a(int i,int j,int k); private int top(int i,int j,int k){ return i *(w +1) *(d +1) +j *(d +1) +k; } long get(int il,int ir,int jl,int jr,int kl,int kr){ return sum[top(ir,jr,kr)] -sum[top(il,jr,kr)] -sum[top(ir,jl,kr)] -sum[top(ir,jr,kl)] +sum[top(ir,jl,kl)] +sum[top(il,jr,kl)] +sum[top(il,jl,kr)] -sum[top(il,jl,kl)]; } } class RangeSet{ private TreeSet set; public RangeSet(){ set = new TreeSet<>(Comparator.comparing(t -> t[0])); long inf = Util.infL; set.add(new long[]{-inf, -inf}); set.add(new long[]{inf, inf}); } public long add(long x){ return add(x,x +1); } public long add(long l,long r){ long ret = r -l; long[] t = {l, r}; for (var s = set.floor(t);t[0] <= s[1];s = set.floor(t)) ret -= add(t,s); for (var s = set.ceiling(t);s[0] <= t[1];s = set.ceiling(t)) ret -= add(t,s); set.add(t); return ret; } public long remove(long x){ return remove(x,x +1); } public long remove(long l,long r){ long ret = 0; long[] t = {l, r}; for (var s = set.floor(t);l < s[1];s = set.floor(t)) ret += remove(t,s); for (var s = set.ceiling(t);s[0] < r;s = set.ceiling(t)) ret += remove(t,s); return ret; } private long add(long[] t,long[] s){ long ret = min(t[1],s[1]) -max(t[0],s[0]); set.remove(s); t[0] = min(t[0],s[0]); t[1] = max(t[1],s[1]); return ret; } private long remove(long[] t,long[] s){ set.remove(s); long ret = min(t[1],s[1]) -max(t[0],s[0]); if (s[0] < t[0]) set.add(new long[]{s[0], t[0]}); if (t[1] < s[1]) set.add(new long[]{t[1], s[1]}); return ret; } public long[] get(long x){ long[] ret = set.floor(new long[]{x}); return x < ret[1] ? ret : null; } public long mex(){ var t = get(0); return t == null ? 0 : t[1]; } public long[][] toArray(){ long[][] ret = new long[set.size() -2][]; long[] x = {set.first()[0]}; for (int i = 0;i < ret.length;i++) x[0] = (ret[i] = set.higher(x))[0]; return ret; } public long cardinality(long l,long r){ long ret = 0; long[] key = {r}; while (l < r) { var t = set.lower(key); if (t[1] <= l) break; ret += min(r,t[1]) -max(l,t[0]); key = t; } return ret; } public long first(){ return set.higher(new long[]{-Util.infL})[0]; } } abstract class BaseV{ public int sz; public boolean fail; } class MyStack extends MyList{ public T pop(){ return remove(size() -1); } public T peek(){ return get(size() -1); } } class MyList implements Iterable{ private T[] arr; private int sz; public MyList(){ this(16); } public MyList(int n){ arr = Util.cast(new Object[max(16,n)]); } public MyList(MyList org){ this(org.sz); System.arraycopy(org.arr,0,arr,0,sz = org.sz); } public boolean isEmpty(){ return sz == 0; } public int size(){ return sz; } public T get(int i){ return arr[i]; } public void add(T t){ (arr = sz < arr.length ? arr : copyOf(arr,sz *5 >>2))[sz++] = t; } public void addAll(MyList list){ for (var t:list) add(t); } public T remove(int i){ var ret = arr[i]; sz--; for (int j = i;j < sz;j++) arr[j] = arr[j +1]; return ret; } public T removeFast(int i){ var ret = arr[i]; arr[i] = arr[--sz]; return ret; } public void sort(){ sort(Util.cast(Comparator.naturalOrder())); } public void sort(Comparator cmp){ Arrays.sort(arr,0,sz,cmp); } public MyList map(Function func){ MyList ret = new MyList<>(sz); forEach(t -> ret.add(func.apply(t))); return ret; } public MyList rev(){ MyList ret = new MyList<>(sz); for (int i = sz;i-- > 0;) ret.add(get(i)); return ret; } public T[] toArray(){ if (sz == 0) return Util.cast(new Object[0]); T[] ret = Util.cast(Array.newInstance(arr[0].getClass(),sz)); System.arraycopy(arr,0,ret,0,sz); return ret; } public void swap(int i,int j){ var t = arr[i]; arr[i] = arr[j]; arr[j] = t; } public void set(int i,T t){ arr[i] = t; } public void clear(){ sz = 0; } @Override public Iterator iterator(){ return new Iterator<>(){ int i = 0; @Override public boolean hasNext(){ return i < sz; } @Override public T next(){ return arr[i++]; } }; } } class BaseSolver extends Util{ public MyReader in; public MyWriter out,log; public BaseSolver(MyReader in,MyWriter out,MyWriter log){ this.in = in; this.out = out; this.log = log; } public int[][] addId(int[][] T){ return arr(new int[T.length][],i -> { int[] t = copyOf(T[i],T[i].length +1); t[t.length -1] = i; return t; }); } public long inv(long x){ return pow(x,mod -2); } public long inv(long x,long mod){ return (extendGcd(x,mod)[0] +mod) %mod; } public long pow(long x,long n){ return pow(x,n,Util.mod); } public long pow(long x,long n,long mod){ long ret = 1; for (x %= mod;0 < n;x = x *x %mod,n >>= 1) if ((n &1) == 1) ret = ret *x %mod; return ret; } public int bSearchI(int o,int n,IntPredicate judge){ for (int m = 0;1 < abs(n -o);) m = judge.test(m = o +n >>1) ? (o = m) : (n = m); return o; } public long bSearchL(long o,long n,LongPredicate judge){ for (long m = 0;1 < abs(n -o);) m = judge.test(m = o +n >>1) ? (o = m) : (n = m); return o; } public double bSearchD(double o,double n,DoublePredicate judge){ for (double m,c = 0;c < 200;c++) m = judge.test(m = (o +n) /2) ? (o = m) : (n = m); return o; } public long gcd(long a,long b){ while (0 < b) { long t = a; a = b; b = t %b; } return a; } public long[] extendGcd(long a,long b){ long x0 = 1,y0 = 0,x1 = 0,y1 = 1; while (b != 0) { long q = a /b,t = a %b,tx = x1,ty = y1; a = b; b = t; x1 = x0 -q *x1; y1 = y0 -q *y1; x0 = tx; y0 = ty; } return new long[]{x0, y0, a}; } public long lcm(long a,long b){ return b /gcd(a,b) *a; } public long ceil(long a,long b){ return (a +b -1) /b; } public int lis(int[] arr){ int[] lis = new int[arr.length]; fill(lis,infI); for (var a:arr) { int i = bSearchI(0,arr.length,ii -> lis[ii] < a) +1; lis[i] = a; } return bSearchI(0,arr.length,i -> lis[i] < infI) +1; } } class Util{ public static String yes = "Yes",no = "No"; public static int infI = (1 <<30) -1; public static long infL = (1L <<61 |1 <<30) -1, mod = 998244353; public static Random rd = ThreadLocalRandom.current(); private long st = System.currentTimeMillis(); protected long elapsed(){ return System.currentTimeMillis() -st; } protected void reset(){ st = System.currentTimeMillis(); } public static int[] arrI(int N,IntUnaryOperator f){ int[] ret = new int[N]; setAll(ret,f); return ret; } public static long[] arrL(int N,IntToLongFunction f){ long[] ret = new long[N]; setAll(ret,f); return ret; } public static double[] arrD(int N,IntToDoubleFunction f){ double[] ret = new double[N]; setAll(ret,f); return ret; } public static T[] arr(T[] arr,IntFunction f){ setAll(arr,f); return arr; } @SuppressWarnings("unchecked") public static T cast(Object obj){ return (T) obj; } } class MyReader{ private byte[] buf = new byte[1 <<16]; private int ptr,tail; private InputStream in; public MyReader(InputStream in){ this.in = in; } private byte read(){ if (ptr == tail) try { tail = in.read(buf); ptr = 0; } catch (IOException e) {} return buf[ptr++]; } private boolean isPrintable(byte c){ return 32 < c && c < 127; } private byte nextPrintable(){ byte ret = read(); while (!isPrintable(ret)) ret = read(); return ret; } public int it(){ return toIntExact(lg()); } public int[] it(int N){ return Util.arrI(N,i -> it()); } public int[][] it(int H,int W){ return Util.arr(new int[H][],i -> it(W)); } public int idx(){ return it() -1; } public int[] idx(int N){ return Util.arrI(N,i -> idx()); } public int[][] idx(int H,int W){ return Util.arr(new int[H][],i -> idx(W)); } public long lg(){ byte i = nextPrintable(); boolean negative = i == 45; long n = negative ? 0 : i -'0'; while (isPrintable(i = read())) n = 10 *n +i -'0'; return negative ? -n : n; } public long[] lg(int N){ return Util.arrL(N,i -> lg()); } public long[][] lg(int H,int W){ return Util.arr(new long[H][],i -> lg(W)); } public double dbl(){ return Double.parseDouble(str()); } public double[] dbl(int N){ return Util.arrD(N,i -> dbl()); } public double[][] dbl(int H,int W){ return Util.arr(new double[H][],i -> dbl(W)); } public char[] ch(){ return str().toCharArray(); } public char[][] ch(int H){ return Util.arr(new char[H][],i -> ch()); } public String line(){ StringBuilder sb = new StringBuilder(); for (byte c;(c = read()) != '\n';) sb.append((char) c); return sb.toString(); } public String str(){ StringBuilder sb = new StringBuilder(); sb.append((char) nextPrintable()); for (byte c;isPrintable(c = read());) sb.append((char) c); return sb.toString(); } public String[] str(int N){ return Util.arr(new String[N],i -> str()); } public String[][] str(int H,int W){ return Util.arr(new String[H][],i -> str(W)); } } class MyWriter{ private OutputStream out; private byte[] buf = new byte[1 <<16],ibuf = new byte[20]; private int tail; private boolean autoflush; public MyWriter(OutputStream out,boolean autoflush){ this.out = out; this.autoflush = autoflush; } public void flush(){ try { out.write(buf,0,tail); tail = 0; } catch (IOException e) { e.printStackTrace(); } } private void ln(){ write((byte) '\n'); if (autoflush) flush(); } private void write(byte b){ buf[tail++] = b; if (tail == buf.length) flush(); } private void write(long n){ if (n < 0) { n = -n; write((byte) '-'); } int i = ibuf.length; do { ibuf[--i] = (byte) (n %10 +'0'); n /= 10; } while (n > 0); while (i < ibuf.length) write(ibuf[i++]); } private void print(Object obj){ if (obj instanceof Boolean) print((boolean) obj ? Util.yes : Util.no); else if (obj instanceof Integer) write((int) obj); else if (obj instanceof Long) write((long) obj); else if (obj instanceof char[]) for (char b:(char[]) obj) write((byte) b); else if (obj.getClass().isArray()) { int l = Array.getLength(obj); for (int i = 0;i < l;i++) { print(Array.get(obj,i)); if (i +1 < l) write((byte) ' '); } } else print(Objects.toString(obj).toCharArray()); } public void println(Object obj){ if (obj == null) obj = "null"; if (obj instanceof Iterable) for (Object e:(Iterable) obj) println(e); else if (obj.getClass().isArray() && Array.getLength(obj) > 0 && Array.get(obj,0).getClass().isArray()) { int l = Array.getLength(obj); for (int i = 0;i < l;i++) println(Array.get(obj,i)); } else { print(obj); ln(); } } public void printlns(Object... o){ print(o); ln(); } }