package main

import (
	"bufio"
	"io"
	"os"
	"strconv"
)

func main() {
	const MAXA = 1000000
	isPrime := make([]bool, MAXA+1)
	for i := 2; i <= MAXA; i++ {
		isPrime[i] = true
	}
	for i := 2; i*i <= MAXA; i++ {
		if isPrime[i] {
			for j := i * i; j <= MAXA; j += i {
				isPrime[j] = false
			}
		}
	}

	data, _ := io.ReadAll(os.Stdin)
	idx := 0
	nextInt := func() int {
		n := len(data)
		for idx < n && (data[idx] < '0' || data[idx] > '9') && data[idx] != '-' {
			idx++
		}
		sign := 1
		if idx < n && data[idx] == '-' {
			sign = -1
			idx++
		}
		val := 0
		for idx < n && data[idx] >= '0' && data[idx] <= '9' {
			val = val*10 + int(data[idx]-'0')
			idx++
		}
		return val * sign
	}

	out := bufio.NewWriter(os.Stdout)
	defer out.Flush()

	t := nextInt()
	for ; t > 0; t-- {
		n := nextInt()
		e := nextInt()
		a := make([]int, n)
		for i := 0; i < n; i++ {
			a[i] = nextInt()
		}
		var ans int64 = 0
		for r := 0; r < e; r++ {
			seg := make([]int, 0, (n-r+e-1)/e)
			for p := r; p < n; p += e {
				seg = append(seg, a[p])
			}
			m := len(seg)
			if m == 0 {
				continue
			}
			L := make([]int, m)
			R := make([]int, m)
			cur := 0
			for i := 0; i < m; i++ {
				v := seg[i]
				if v == 1 {
					cur++
				} else {
					if isPrime[v] {
						L[i] = cur
					}
					cur = 0
				}
			}
			cur = 0
			for i := m - 1; i >= 0; i-- {
				v := seg[i]
				if v == 1 {
					cur++
				} else {
					if isPrime[v] {
						R[i] = cur
					}
					cur = 0
				}
			}
			for i := 0; i < m; i++ {
				v := seg[i]
				if v != 1 && isPrime[v] {
					l := L[i]
					rv := R[i]
					ans += int64(l + rv + l*rv)
				}
			}
		}
		out.WriteString(strconv.FormatInt(ans, 10))
		out.WriteByte('\n')
	}
}