// Justin Almazan
// 7/21/2025
// Solution to 2025 CP SI @ UCF Contest 4 Problem: Matching Strings

import java.io.*;
import java.util.*;

public class matching {

    static int tt, n, x;
    static String s;
    static final long[] MOD = { 998_244_353L, 1_000_000_009L, 1_000_000_023L };
    static final long[] q = { inv(27, 0), inv(27, 1), inv(27, 2) };

    // Computes mod inverse of a number in log(MOD) time
    public static long inv(long a, int idx) {
        return (a <= 1 ? a : MOD[idx] - (MOD[idx] / a) * inv(MOD[idx] % a, idx) % MOD[idx]);
    }

    public static void main(String[] args) throws Exception {

        // Test cases
        Scanner sc = new Scanner(System.in);
        tt = sc.nextInt();
        
        // Process test cases
        while (tt-->0) {

            // Get input
            s = sc.next();
            n = s.length();
            x = sc.nextInt();

            // These will store our hash values and the 27^x % MOD
            long [] v = {0L, 0L, 0L};
            long [] p = {1L, 1L, 1L};
            long [] q = {inv(27, 0), inv(27, 1), inv(27, 2)};

            // Build up the first substring of length x
            for (int i = 0; i < x; i++) {

                // Convert to int
                long value = (long)(s.charAt(i) - 'a') + 1;

                // Add to each hash
                for (int j = 0; j < 3; j++) {
                    v[j] += p[j] * value;
                    v[j] %= MOD[j];
                    p[j] *= 27;
                    p[j] %= MOD[j];
                }
            }

            // Insert into map (keeps track of frequencies for each set of hashes)
            TreeMap<Tuple, Integer> map = new TreeMap<Tuple, Integer>();
            Tuple hashes = new Tuple(v[0], v[1], v[2]);
            map.put(hashes, map.getOrDefault(hashes, 0) + 1);

            // Adjust powers of 27
            for (int i = 0; i < 3; i++)
                p[i] = (p[i] * q[i]) % MOD[i];

            // Create all other hashes for strings of length x
            for (int i = x; i < n; i++) {

                // Convert to int
                long value = (long)(s.charAt(i) - 'a') + 1;

                // Change each hash
                for (int j = 0; j < 3; j++) {

                    // Take out beginning character
                    v[j] -= (long)(s.charAt(i-x) - 'a') + 1;
                    v[j] += MOD[j];
                    v[j] %= MOD[j];
                    v[j] *= q[j];
                    v[j] %= MOD[j];

                    // Add new character to end
                    v[j] += p[j] * value;
                    v[j] %= MOD[j];
                }

                // Insert into map
                hashes = new Tuple(v[0], v[1], v[2]);
                map.put(hashes, map.getOrDefault(hashes, 0) + 1);
            }

            // Stores our answer
            int res = 0;

            // Loop through all hashes and add to res if it appears multiple times
            for (int count : map.values())
                if (count >= 2)
                    res++;
            
            // Print answer
            System.out.println(res);
        }
    }

    // Class to store the 3 different hashes
    public static class Tuple implements Comparable<Tuple> {
        long x, y, z;

        Tuple(long x, long y, long z) {
            this.x = x;
            this.y = y;
            this.z = z;
        }

        @Override public int compareTo(Tuple o) {
            if (x != o.x) return Long.compare(x, o.x);
            if (y != o.y) return Long.compare(y, o.y);
            return Long.compare(z, o.z);
        }
    }
}