N = 10**6+1
is_prime = [1]*N
is_prime[0] = 0
is_prime[1] = 0
def sieve():
i = 2
while i*i <= N:
if is_prime[i] == 0:
i += 1
continue
j = 2*i
while j < N:
is_prime[j] = 0
j += i
i += 1
sieve()
lstp=[]
for i in range(1, N):
if is_prime[i] == 1:
lstp.append(i)
se=set(lstp)
t=int(input())
for i in range(t):
n,e=map(int,input().split())
lst=list(map(int,input().split()))
ones=[]
primes=[]
for j in range(n):
ele=lst[j]
if ele==1:
ones.append(j+1)
elif ele in se:
primes.append(j+1)
c=0
for j in primes:
ele=lst[j-1]
right=0
left=0
for f in range(j+e-1,n,e):
if lst[f]==1:
right+=1
else:
break
for f in range(j-e-1,-1,-e):
if lst[f]==1:
left+=1
else:
break
c+=(((left+1)*(right+1))-1)
print(c)#include<bits/stdc++.h>
#define ORIGNAL_SENSEI ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
using namespace std;
typedef long long ll;
typedef long double ld;
const ll MOD=1e9+7, OO=0x3f3f3f3f;
const ll LOO=0x3f3f3f3f3f3f3f3f;
#define all(x) (x).begin(),(x).end()
#define mm(f, x) memset(f,x,sizeof(f))
#define f(n) for(int i=0;i<n;++i)
#define fa(i,a,n) for(int i=(a);i<=(n);++i)
#define c(vec) for(auto &x:vec)cin>>x;
#define ff(vec) for(auto &x:vec)cout<<x<<' ';cout<<'\n';
#define debug(x) cout<<#x<<":"<<x<<endl;
#define yes cout<<"YES\n";
#define no cout<<"NO\n";
//#define f(n,m) for(int i=0;i<n;i++)for(int j=0;j<m;j++)
const long double EPS=1e-8;
const ll MOD1=1e18+7;
int dr[]={-1, -1, -1, 0, 1, 1, 1, 0};
int dc[]={-1, 0, 1, 1, 1, 0, -1, -1};
int dx[]={1,0,-1,0};
int dy[]={0,1,0,-1};
int prime[1000005];
void sieve(){
prime[0]=prime[1]=1;
for(int i=2;i*i<1000001;i+=((i%2)+1)){
if(prime[i]==0)
for(int j=i*i;j<1000001;j+=i){
prime[j]=1;
}
}
}
int main() {
ORIGNAL_SENSEI
//freopen("input.txt","rt",stdin);
//freopen("output.txt","wt",stdout);
int t;
cin>>t;
sieve();
while(t--){
int n,e;
cin>>n>>e;
vector<int>vec(n);
c(vec)
vector<int>ans;
f(n){
if(prime[vec[i]]==0)ans.push_back(i);
}
map<ll,ll>mp;
for(auto i:ans){
ll cnt=0;
ll val=vec[i];
if(val==1) {
bool flag=0;
for (int j = i + e; j < n; j += e) {
if(flag&&vec[j]==1)cnt++;
else if(vec[j]==1)continue;
else if(prime[vec[j]]==1||flag)break;
else if(prime[vec[j]]==0){
cnt++;
flag=1;
}
}
}
else if(prime[val]==0){
for (int j = i + e; j < n; j += e) {
if(vec[j]==1)cnt++;
else break;
}
}
mp[i]=cnt;
}
for(auto i:ans){
ll c=0;
ll val=vec[i];
if(val==1) {
bool flag=0;
for (int j = i - e; j >= 0; j -= e) {
if(flag&&vec[j]==1)c++;
else if(vec[j]==1)continue;
else if(prime[vec[j]]==1||flag)break;
else if(prime[vec[j]]==0){
c++;
flag=1;
}
}
}
else if(prime[val]==0){
for (int j = i - e; j >=0; j -= e) {
if(vec[j]==1)c++;
else break;
}
}
if(c!=0){
mp[i]+=(c*mp[i]+c);
}
}
ll cnt=0;
for(auto x:mp)cnt+=x.second;
cout<<cnt<<'\n';
}
}1553C - Penalty | 1474E - What Is It |
1335B - Construct the String | 1004B - Sonya and Exhibition |
1397A - Juggling Letters | 985C - Liebig's Barrels |
115A - Party | 746B - Decoding |
1424G - Years | 1663A - Who Tested |
1073B - Vasya and Books | 195B - After Training |
455A - Boredom | 1099A - Snowball |
1651D - Nearest Excluded Points | 599A - Patrick and Shopping |
237A - Free Cash | 1615B - And It's Non-Zero |
1619E - MEX and Increments | 34B - Sale |
1436A - Reorder | 1363C - Game On Leaves |
1373C - Pluses and Minuses | 1173B - Nauuo and Chess |
318B - Strings of Power | 1625A - Ancient Civilization |
864A - Fair Game | 1663B - Mike's Sequence |
448A - Rewards | 1622A - Construct a Rectangle |