#include <bits/stdc++.h>
using namespace std;

#define begin_code_from_here ios_base::sync_with_stdio(false); cin.tie(NULL);


bool prime[1000000+1];

void Sieve()
{
    long long n = 1000000;
    memset(prime, true, sizeof(prime));
 
    for (long long p = 2; p * p <= n; p++)
    {
        if (prime[p] == true)
        {
            for (long long i = p * p; i <= n; i += p)
                prime[i] = false;
        }
    }
 
}
 

int main(){    
    begin_code_from_here

    Sieve();
    long long t;
    cin >> t;
    while(t--){
        long long n,e;
        cin >> n >> e;
        vector<long long> a(n+1);
        for(long long i = 1 ; i <=n ; i++) cin >> a[i];
        vector<vector<long long>> dp(n+1,vector<long long>(2));
        //dp[n+1] = {-1,-1};
        /*
        DP state : { index of prime no. > 1, last index of one}
        */

        for(long long i = n ; i >= 1 ; i--){
            if(prime[a[i]]){
                if(a[i] > 1){
                    if(i+e <= n){
                        if(!prime[a[i+e]]){
                            dp[i] = dp[i+e];
                            dp[i][0] = i;
                            continue;
                        }
                        auto last_state = dp[i+e];
                        if(last_state[0] != -1){
                            // we already have a prime num in this streal
                            dp[i][0] = i;
                            dp[i][1] = dp[i+e][0] - e;
                            if(dp[i][1] == i){
                                dp[i][1] = -1;
                            }
                        }
                        else{                                                        
                            dp[i][1] = dp[i+e][1];
                            dp[i][0] = i;
                        }
                    }
                    else{
                        dp[i][0] = i;
                        dp[i][1] = -1;
                    }
                }
                else{
                    if(i+e <= n){
                        if(!prime[a[i+e]]){
                            dp[i] = dp[i+e];
                            dp[i][1] = i;
                            continue;
                        }
                        dp[i][0] = dp[i+e][0];
                        dp[i][1] = dp[i+e][1];
                    }
                    else {
                        dp[i][0] = -1;
                        dp[i][1] = i;
                    }
                }
            }
            else{
                dp[i] = {-1,-1};
            }
        }


        long long ans = 0;
        for(long long i = 1 ; i <= n ;i++){
            if(prime[a[i]]){
                if((dp[i][0] == -1 && a[i] == 1) || (dp[i][0] == -1 && dp[i][1] == -1)){
                    continue;
                }
                else{
                    long long mx_pos=i;                 
                    if(a[i] == 1){
                        if(dp[i][1] < dp[i][0]){
                            ans++;
                        }
                        else{
                            ans += (dp[i][1] - dp[i][0])/e + 1;
                        }
                    }
                    else{                        
                        mx_pos = max(mx_pos,dp[i][0]);                                        
                        mx_pos = max(mx_pos,dp[i][1]);     
                        ans += (mx_pos-i) / e;                        
                    }
                }
            }
        }
        cout << ans << "\n";
    }
    
    return 0;
}