Jigar got a sequence of n positive integers as his birthday present! He likes consecutive subsequences whose sum is divisible by k. He asks you to write a program to count them for him.

Input Format 

The first line contains T, the number of testcases. 

T testcases follow. Each testcase consists of 2 lines. 

The first line contains n and k separated by a single space. 

And the second line contains n space separated integers.

Output Format 

For each test case, output the number of consecutive subsequenences whose sum is divisible by k in a newline.

Constraints 

1 ≤ T ≤ 20 

1 ≤ n ≤ 10^{6} 

1 ≤ k ≤ 100 

1 ≤ a[i] ≤ 10^{4} 

Sample Input

2
5 3
1 2 3 4 1
6 2
1 2 1 2 1 2

Sample Output

4
9

Explanation

For 

1 2 3 4 1

there exists, 4 subsequences whose sum is divisible by 3, they are   

3
1 2
1 2 3
2 3 4

For 

1 2 1 2 1 2

there exists, 9 subsequences whose sum is divisible by 2, they are  

2
2
2
1 2 1
1 2 1
1 2 1 2
2 1 2 1
1 2 1 2
2 1 2 1 2

Difficulty: MEDIUM
Tags: Combinatorics

Starter code:

Solutions:
import itertools

def one_test(a, k):
	a = itertools.accumulate(map(lambda x: x % k, a), lambda x, y: (x + y) % k)
	cnt = [0] * k
	for x in a:
		cnt[x] += 1
	return sum((x * (x - 1) // 2 for x in cnt))
t = int(input())
for _ in range(t):
	(n, k) = map(int, input().split())
	a = itertools.chain([0], map(int, input().split()))
	print(one_test(a, k))


t = int(input())
for khfs in range(t):
	s = input().strip().split()
	n = int(s[0])
	k = int(s[1])
	st = input().strip().split()
	d = {0: 0}
	sum = 0
	for i in st:
		sum += int(i)
		rem = sum % k
		try:
			d[rem] += 1
		except KeyError:
			d[rem] = 1
	ans = 0
	for j in range(k):
		try:
			m = d[j]
			ans += m * (m - 1) // 2
		except KeyError:
			pass
	ans += d[0]
	print(ans)


import collections, itertools, sys
T = int(sys.stdin.readline())
for _ in range(T):
	(N, K) = list(map(int, sys.stdin.readline().split()))
	A = list(map(int, sys.stdin.readline().split()))
	x = collections.Counter((n % K for n in itertools.accumulate(A)))
	x[0] += 1
	print(sum(((x[i] - 1) * x[i] // 2 for i in range(K))))


def sumTo(n):
	return n * (n + 1) // 2
for case in range(int(input())):
	(n, k) = map(int, input().split())
	arr = map(int, input().split())
	numMod = [0] * k
	s = 0
	for i in arr:
		s += i
		numMod[s % k] += 1
	numMod[0] += 1
	answer = 0
	for i in numMod:
		answer += sumTo(i - 1)
	print(answer)


import collections, itertools, sys
T = int(sys.stdin.readline())
for _ in range(T):
	(N, K) = list(map(int, sys.stdin.readline().split()))
	A = list(map(int, sys.stdin.readline().split()))
	prefix_mod = [1] + [0] * (K - 1)
	prefix = 0
	for a in A:
		prefix = (prefix + a) % K
		prefix_mod[prefix] += 1
	print(sum(((prefix_mod[i] - 1) * prefix_mod[i] // 2 for i in range(K))))


import collections, itertools, sys
T = int(sys.stdin.readline())
for _ in range(T):
	(N, K) = list(map(int, sys.stdin.readline().split()))
	A = list(map(int, sys.stdin.readline().split()))
	prefix_mod = [1] + [0] * (K - 1)
	prefix = 0
	for a in A:
		prefix = (prefix + a) % K
		prefix_mod[prefix] += 1
	print(sum(((prefix_mod[i] - 1) * prefix_mod[i] // 2 for i in range(K))))


import collections, itertools, sys
T = int(sys.stdin.readline())
for _ in range(T):
	(N, K) = list(map(int, sys.stdin.readline().split()))
	A = list(map(int, sys.stdin.readline().split()))
	prefix_mod = [1] + [0] * (K - 1)
	prefix = 0
	for a in A:
		prefix = (prefix + a) % K
		prefix_mod[prefix] += 1
	print(sum(((prefix_mod[i] - 1) * prefix_mod[i] // 2 for i in range(K))))


import collections, itertools, sys
T = int(sys.stdin.readline())
for _ in range(T):
	(N, K) = list(map(int, sys.stdin.readline().split()))
	A = list(map(int, sys.stdin.readline().split()))
	prefix_mod = [1] + [0] * (K - 1)
	prefix = 0
	for a in A:
		prefix = (prefix + a) % K
		prefix_mod[prefix] += 1
	print(sum(((prefix_mod[i] - 1) * prefix_mod[i] // 2 for i in range(K))))


import collections, itertools, sys
T = int(sys.stdin.readline())
for _ in range(T):
	(N, K) = list(map(int, sys.stdin.readline().split()))
	A = list(map(int, sys.stdin.readline().split()))
	prefix_mod = [1] + [0] * (K - 1)
	prefix = 0
	for a in A:
		prefix = (prefix + a) % K
		prefix_mod[prefix] += 1
	print(sum(((prefix_mod[i] - 1) * prefix_mod[i] // 2 for i in range(K))))


def num_seq(L, d):
	rem = {}
	for i in range(d):
		rem[i] = 0
	for i in range(1, len(L)):
		L[i] += L[i - 1]
	answer = 0
	for i in L:
		k = i % d
		if k == 0:
			answer += 1
		answer += rem[k]
		rem[k] += 1
	return answer
numTrials = int(input())
for i in range(numTrials):
	d = int(input().split()[1])
	L = input().split()
	L = [int(i) for i in L]
	print(num_seq(L, d))


t = int(input())
for _ in range(t):
	(n, k) = list(map(int, input().split()))
	R = [0] * k
	R[0] = 1
	s = 0
	lis = list(map(int, input().split()))
	for x in lis:
		s += x
		s = s % k
		R[s] += 1
	res = 0
	for x in R:
		res += x * (x - 1) // 2
	print(res)


def nC2(n):
	return n * (n - 1) // 2
for _ in range(int(input())):
	(n, k) = map(int, input().split())
	array = map(int, input().split())
	running_sum = 0
	counts = {0: 1}
	for i in range(1, k):
		counts[i] = 0
	for num in array:
		running_sum = (running_sum + num) % k
		counts[running_sum] += 1
	print(sum(map(nC2, counts.values())))


from sys import stdin
from itertools import accumulate as acc, count, combinations_with_replacement as cmbrep, takewhile as tkw, repeat as rp, dropwhile as dpw, combinations as comb
from functools import reduce
from random import randint
from collections import Counter
from math import sqrt, log, factorial
from fractions import gcd
from heapq import merge
from array import array
filou = None
rd = open(filou) if filou else stdin
for _ in range(int(rd.readline().strip())):
	(Ln, K) = map(int, rd.readline().strip().split())
	A = [0] + list(map(int, rd.readline().strip().split()))
	cnt = Counter(acc(A, lambda x, y: (x + y) % K))
	print(sum((v * (v - 1) // 2 for v in cnt.values())))


import sys

def c(n, m):
	rval = 1
	for i in range(m):
		rval *= n - i
		rval //= i + 1
	return rval

def solve(aa, k):
	sm = 0
	sma = [0]
	for a in aa:
		sm += a
		sm %= k
		sma.append(sm)
	cache = [0] * k
	for v in sma:
		cache[v] += 1
	cnt = 0
	for v in cache:
		if v > 1:
			cnt += c(v, 2)
	return cnt
t = int(input())
for _ in range(t):
	(_, k) = map(int, input().split())
	aa = list(map(int, input().split()))
	print(solve(aa, k))


for _ in range(int(input())):
	(N, K) = list(map(int, input().split()))
	ar = list(map(int, input().split()))
	cnt = {}
	res = 0
	s = 0
	for item in ar:
		s = (s + item) % K
		res += s == 0
		if not s in cnt:
			cnt[s] = 1
		else:
			cnt[s] += 1
	for item in cnt:
		if cnt[item] > 1:
			res += cnt[item] * (cnt[item] - 1) // 2
	print(res)


t = int(input().strip())
for i in range(t):
	(n, k) = input().strip().split(' ')
	k = int(k)
	n = int(n)
	arr = [int(b) for b in input().strip().split(' ')]
	cnts = [0 for _ in range(k)]
	s = 0
	cnts[0] = 1
	for num in arr:
		s += num
		s %= k
		cnts[s] += 1
	result = 0
	for cnt in cnts:
		result += cnt * (cnt - 1) / 2
	print(int(result))


T = int(input())
for t in range(T):
	Z = input().split()
	(n, k) = (int(Z[0]), int(Z[1]))
	A = input().split()
	parSum = [0] * n
	have = [0] * k
	parSum[0] = int(A[0])
	have[parSum[0] % k] += 1
	for i in range(1, n):
		parSum[i] = parSum[i - 1] + int(A[i])
		have[parSum[i] % k] += 1
	ans = 0
	for i in range(k):
		ans += have[i] * (have[i] - 1) / 2
	ans += have[0]
	print(int(ans))


t = int(input())
for i in range(t):
	L = list(map(int, input().split()))
	n = L[0]
	k = L[1]
	L = list(map(int, input().split()))
	F = []
	for j in range(k):
		F.append(0)
	F[0] = 1
	s = 0
	for j in range(n):
		s += L[j]
		F[s % k] += 1
	s = 0
	for j in range(k):
		s += F[j] * (F[j] - 1) / 2
	print(int(s))


import sys
import itertools
T = int(input().strip())
for i in range(T):
	(N, K) = map(int, sys.stdin.readline().split())
	X = map(int, sys.stdin.readline().split())
	A = list(itertools.accumulate(X))
	S = [0] * (K + 1)
	S[0] = 1
	for v in A:
		S[v % K] += 1
	total = 0
	for v in S:
		total += v * (v - 1) // 2
	print(total)


t = int(input())
for T in range(t):
	(n, k) = input().split()
	(n, k) = (int(n), int(k))
	l = input().split()
	l = list(map(int, l))
	K = [0 for i in range(k)]
	s = 0
	for i in l:
		s += i
		s %= k
		K[s] += 1
	print(K[0] + sum((ki * (ki - 1) // 2 for ki in K)))


t = int(input())
while t:
	(n, k) = map(int, input().split())
	arr = [int(x) for x in input().split()]
	c = 0
	s = 0
	arr1 = [0] * k
	arr1[0] = 1
	s = 0
	for i in range(0, n):
		s += arr[i]
		s %= k
		arr1[s] += 1
	for i in range(k):
		c += arr1[i] * (arr1[i] - 1) // 2
	print(c)
	t -= 1


T = int(input())
for t in range(T):
	(n, k) = map(int, input().split())
	a = [int(x) for x in input().split()]
	c = [0] * k
	c[0] = 1
	s = 0
	for x in a:
		s = (s + x) % k
		c[s] += 1
	s = 0
	for x in c:
		s += x * (x - 1) // 2
	print(s)


from collections import Counter
from sys import stdin
readl = stdin.readline
for _ in range(int(readl())):
	(n, k) = map(int, readl().split())
	arr = [0] + list(map(lambda s: int(s) % k, readl().split()))
	s = arr[0]
	acc = [0] * (n + 1)
	for i in range(1, n + 1):
		s = (s + arr[i]) % k
		acc[i] = s
	c = Counter(acc)
	r = sum(map(lambda x: (x - 1) * x // 2, c.values()))
	print(r)


from collections import Counter
from itertools import accumulate
for _ in range(int(input())):
	(n, k) = map(int, input().split())
	A = map(int, ('0 ' + input()).split())
	Asum = Counter(accumulate(A, lambda x, y: (x + y) % k))
	m = sum((n * (n - 1) // 2 for n in Asum.values()))
	print(m)


for _ in range(int(input().strip())):
	(n, k) = map(int, input().split())
	arr = list(map(int, input().split()))
	s = 0
	c = 0
	m = [1] + [0] * (k - 1)
	for j in range(n):
		s = (s + arr[j] % k) % k
		m[s] += 1
	ans = 0
	for i in range(k):
		if m[i] > 1:
			ans += m[i] * (m[i] - 1) // 2
	print(ans)


t = int(input())
for _ in range(t):
	(n, k) = list(map(int, input().split()))
	pre = [0] * n
	l = list(map(int, input().split()))
	count = [0] * k
	pre[0] = l[0]
	for i in range(1, n):
		pre[i] = l[i] + pre[i - 1]
	count[0] = 1
	for i in pre:
		count[i % k] += 1
	res = 0
	for i in count:
		res += i * (i - 1) // 2
	print(res)


T = int(input())
for run in range(T):
	(n, k) = [int(i) for i in input().split()]
	cn = [0] * k
	cn[0] = 1
	s = 0
	for i in input().split():
		s = (s + int(i)) % k
		cn[s] += 1
	s = 0
	for i in cn:
		s += i * (i - 1) // 2
	print(s)


num_probs = int(input())
for prob in range(num_probs):
	(n, k) = (int(x) for x in input().split())
	X = [int(x) for x in input().split()]
	count = [0 for i in range(k)]
	count[0] = 1
	s = 0
	for x in X:
		s = (s + x) % k
		count[s] += 1
	pairs = [i * (i - 1) // 2 for i in count]
	print(sum(pairs))


def count_div(a, k):
	sums = {0: 1}
	cur_sum = 0
	for x in a:
		cur_sum = (cur_sum + x) % k
		sums[cur_sum] = sums.get(cur_sum, 0) + 1
	return sum((x * (x - 1) // 2 for x in sums.values()))
T = int(input())
for t in range(T):
	(n, k) = map(int, input().split())
	a = [int(x) for x in input().split()]
	print(count_div(a, k))


test_n = int(input())
cases = []
for _ in range(test_n):
	(n, k) = [int(x) for x in input().split(' ')]
	v = [int(x) for x in input().split(' ')]
	cases.append((n, k, v))

def get_seq(n, k, arr):
	rem = [0] * k
	cum_sum = 0
	for i in range(n):
		cum_sum += arr[i]
		rem[cum_sum % k] += 1
	count = 0
	for i in range(k):
		if rem[i] > 1:
			count += rem[i] * (rem[i] - 1) / 2
	count += rem[0]
	return int(count)
for (n, k, v) in cases:
	print(get_seq(n, k, v))


import collections, itertools, sys
T = int(sys.stdin.readline())
for _ in range(T):
	(N, K) = list(map(int, sys.stdin.readline().split()))
	A = list(map(int, sys.stdin.readline().split()))
	prefix_mod = [1] + [0] * (K - 1)
	prefix = 0
	for a in A:
		prefix = (prefix + a) % K
		prefix_mod[prefix] += 1
	print(sum(((prefix_mod[i] - 1) * prefix_mod[i] // 2 for i in range(K))))


from collections import Counter
for _ in range(int(input())):
	(n, k) = [int(x) for x in input().split()]
	ns = [int(x) for x in input().split()]
	s = [0]
	for n in ns:
		s.append((s[-1] + n) % k)
	c = Counter(s)
	res = 0
	for (k, v) in c.items():
		res += v * (v - 1) // 2
	print(res)


t = int(input())
for _ in range(t):
	(n, k) = map(int, input().split())
	d = list(map(int, input().split()))
	p = [0]
	s = 0
	for i in d:
		s += i
		s %= k
		p.append(s)
	m = {}
	for i in p:
		if i in m:
			m[i] += 1
		else:
			m[i] = 0
	res = 0
	for i in m:
		res += m[i] * (m[i] + 1) // 2
	print(res)


T = int(input())

def nchoosek(n, k):
	choose = 1
	for i in range(0, k):
		choose *= n - i
		choose //= i + 1
	return choose
for cases in range(0, T):
	(n, k) = [int(a) for a in input().split()]
	A = [int(a) for a in input().split()]
	K_vec = [0 for i in range(0, k)]
	running_sum = 0
	K_vec[0] += 1
	for i in range(0, n):
		running_sum += A[i]
		running_sum %= k
		K_vec[running_sum] += 1
	total = 0
	for i in range(0, k):
		total += nchoosek(K_vec[i], 2)
	print(total)


T = int(input())
for _ in range(T):
	a = list(map(int, input().split()))
	n = a[0]
	k = a[1]
	F = list(map(int, input().split()))
	pre = [0] * n
	pre[0] = F[0]
	for i in range(1, n):
		pre[i] = F[i] + pre[i - 1]
	count = [0] * 111
	count[0] = 1
	for i in range(0, n):
		count[pre[i] % k] += 1
	sum = 0
	for i in range(0, 110 + 1):
		sum += count[i] * (count[i] - 1) // 2
	print(sum)


def readints():
	return [int(s) for s in input().split(' ')]
t = int(input())
for _ in range(t):
	(n, k) = readints()
	a = readints()
	cumSumRes = [0]
	for x in a:
		cumSumRes.append((cumSumRes[-1] + x) % k)
	resCounts = [0 for _ in range(k)]
	for res in cumSumRes:
		resCounts[res] += 1
	result = 0
	for count in resCounts:
		result += count * (count - 1) // 2
	print(result)


def solve(arr, k):
	k_ost = [0] * k
	k_ost[0] = 1
	slide_sum = 0
	for v in arr:
		slide_sum = (slide_sum + v) % k
		k_ost[slide_sum] += 1
	result = 0
	for v in k_ost:
		result += v * (v - 1) // 2
	return result
for _ in range(int(input())):
	(_, k) = map(int, input().split())
	arr = [int(i) for i in input().split()]
	print(solve(arr, k))


def main():
	T = int(input())
	for _ in range(T):
		(n, k) = map(int, input().split())
		A = list(map(int, input().split()))
		R = [0] * k
		R[0] = 1
		s = 0
		res = 0
		for i in range(n):
			s = (s + A[i]) % k
			res += R[s]
			R[s] += 1
		print(res)
main()


from collections import defaultdict
T = int(input())
for t in range(T):
	(n, k) = list(map(int, input().split()))
	arr = list(map(int, input().split()))
	visit = defaultdict(lambda : 0)
	visit[0] = 1
	(acc, ans) = (0, 0)
	for num in arr:
		acc += num
		acc %= k
		ans += visit[acc]
		visit[acc] += 1
	print(ans)


from collections import defaultdict
tc = int(input())
for t in range(tc):
	(n, k) = map(int, input().split())
	arr = list(map(int, input().split()))
	arr = [x % k for x in arr]
	dp = defaultdict(int)
	dp[0] = 1
	curr_sum = 0
	ans = 0
	for el in arr:
		curr_sum += el
		if curr_sum % k in dp:
			ans += dp[curr_sum % k]
		dp[curr_sum % k] += 1
	print(ans)


def consecdiv0(n, k, arr):
	pre = []
	pre.append(arr[0])
	for i in range(1, n):
		pre.append(arr[i] + pre[i - 1])
	count = [0] * n
	count[0] = 1
	for i in range(n):
		count[pre[i] % k] += 1
	sum = 0
	for i in range(n):
		sum += count[i] * (count[i] - 1) // 2
	return sum

def consecdiv(n, k, arr):
	prefixModCount = [0 for _ in range(k)]
	prefixModCount[0] = 1
	prefixSum = 0
	for i in range(n):
		prefixSum += arr[i]
		idx = prefixSum % k
		prefixModCount[idx] += 1
	result = 0
	for mod in range(k):
		result += prefixModCount[mod] * (prefixModCount[mod] - 1) // 2
	return result

def main():
	TEST = 0
	t = int(input().strip())
	for _ in range(t):
		arr1 = list(map(int, input().rstrip().split()))
		n = arr1[0]
		k = arr1[1]
		arr = list(map(int, input().rstrip().split()))
		ans = consecdiv(n, k, arr)
		print(ans)
main()


t = int(input())
while t > 0:
	(n, k) = list(map(int, input().split()))
	A = map(int, input().rstrip().split())
	s = 0
	n = [0 for i in range(k)]
	for el in A:
		j = el % k
		n = n[k - j:] + n[:k - j]
		n[j] += 1
		s += n[0]
	print(s)
	t -= 1


def count_subseq(seq, k):
	n = len(seq)
	prefix_sums = seq[:]
	for i in range(1, n):
		prefix_sums[i] += prefix_sums[i - 1]
	freq = [0] * k
	for num in prefix_sums:
		freq[num % k] += 1
	seq = [num % k for num in seq]
	count = freq[0]
	for num in seq:
		freq[num] -= 1
		freq = left_shift(freq, num)
		count += freq[0]
	return count

def left_shift(lst, s):
	s = s % len(lst)
	return lst[s:] + lst[:s]

def count_subseq_slow(a, k):
	n = len(a)
	count = 0
	for i in range(n):
		running_total = 0
		for j in range(i, n):
			running_total += a[j]
			if running_total % k == 0:
				count += 1
	return count
t = int(input())
for _ in range(t):
	(n, k) = [int(a) for a in input().split()]
	seq = [int(a) for a in input().split()]
	print(count_subseq(seq, k))


def count_pairs(seq, k):
	seq = [num % k for num in seq]
	freq = [0] * k
	prefix_sum = 0
	for num in seq:
		prefix_sum += num
		freq[prefix_sum % k] += 1
	count = freq[0]
	for num in seq:
		freq[num] -= 1
		freq = freq[num:] + freq[:num]
		count += freq[0]
	return count
T = int(input())
for _ in range(T):
	(n, k) = [int(a) for a in input().split()]
	seq = [int(a) for a in input().split()]
	print(count_pairs(seq, k))


from collections import defaultdict

def solve(a, k):
	sums = [0] * (len(a) + 1)
	s = 0
	sums[0] = 0
	for (i, ai) in enumerate(a, start=1):
		s += ai
		sums[i] = s
	a = sums
	a = [ai % k for ai in a]
	c = [[0] * k for _ in range(2)]
	res = 0
	counts = defaultdict(int)
	for ai in a:
		res += counts[ai]
		counts[ai] += 1
	return res
t = int(input())
for _ in range(t):
	(n, k) = map(int, input().split())
	a = list(map(int, input().split()))
	print(solve(a, k))


for _ in range(int(input())):
	(N, K) = map(int, input().split(' '))
	(D, DL, C, r) = ([0] * (N + 1), input().split(' '), [0] * K, 0)
	C[0] = 1
	for i in range(N):
		D[i + 1] = (D[i] + int(DL[i])) % K
		C[D[i + 1]] += 1
	for c in C:
		if c > 1:
			r = r + (c * (c - 1) >> 1)
	print(r)


t = int(input())
for _ in range(t):
	(n, k) = map(int, input().split())
	l = map(int, input().split())
	w = {i: 0 for i in range(k)}
	w[0] = 1
	s = 0
	for x in l:
		s = (s + x) % k
		w[s] += 1
	print(sum(((w[x] * w[x] - w[x]) // 2 for x in w)))


N = int(input())
for _ in range(N):
	(n, k) = tuple(map(int, input().split(' ')))
	values = list(map(int, input().split(' ')))
	prefixes = [0] * k
	prefixes[0] = 1
	total = 0
	for value in values:
		total = (total + value) % k
		prefixes[total] += 1
	output = 0
	for prefix in prefixes:
		output += (prefix - 1) * prefix // 2
	print(output)


def subcount(arr, n, k):
	mod = []
	for i in range(k + 1):
		mod.append(0)
	cumSum = 0
	for i in range(n):
		cumSum = cumSum + arr[i]
		mod[(cumSum % k + k) % k] = mod[(cumSum % k + k) % k] + 1
	result = 0
	for i in range(k):
		if mod[i] > 1:
			result = result + mod[i] * (mod[i] - 1) // 2
	result = result + mod[0]
	return result
for i in range(0, int(input())):
	nk = input().split()
	n = int(nk[0])
	k = int(nk[1])
	count = 0
	l = list(map(int, input().split()))
	print(subcount(l, n, k))


from itertools import accumulate
t = int(input())
for i in range(t):
	s = input().split()
	n = int(s[0])
	k = int(s[1])
	arr = list(map(int, input().split()))
	acc = list(accumulate(arr))
	s = 0
	a = [0] * k
	a[0] = 1
	for i in acc:
		x = i % k
		a[x] += 1
	for i in a:
		s += i * (i - 1) / 2
	print(int(s))


import os
from itertools import accumulate
for i in range(int(input())):
	(n, x) = map(int, input().split())
	l = list(map(int, input().split()))
	s = list(accumulate(l))
	d = [0] * x
	d[0] = 1
	for i in s:
		d[i % x] += 1
	j = 0
	for i in range(len(d)):
		m = d[i]
		j += m * (m - 1) // 2
	print(j)


from sys import *
for _ in range(int(stdin.readline())):
	(n, k) = map(int, stdin.readline().split())
	a = list(map(int, stdin.readline().split()))
	c = [0] * k
	c[0] = 1
	pre = [0] * n
	pre[0] = a[0]
	for i in range(1, n):
		pre[i] = a[i] + pre[i - 1]
	for i in range(0, n):
		c[pre[i] % k] += 1
	sum = 0
	for i in range(k):
		sum += c[i] * (c[i] - 1) // 2
	print(sum)


t = int(input())
for _ in range(t):
	s = input().split()
	n = int(s[0])
	k = int(s[1])
	a = list(map(int, input().split()))
	m = [0] * k
	m[0] = 1
	s1 = 0
	for i in a:
		s1 += i
		if s1 % k == 0:
			m[0] += 1
			s1 = 0
		else:
			m[s1 % k] += 1
	res = 0
	for i in range(k):
		res += m[i] * (m[i] - 1) // 2
	print(res)


def ncr(n):
	cr = 1
	for i in range(2):
		cr = cr * (n - i)
		cr /= i + 1
	return int(cr)
t = int(input())
while t:
	t -= 1
	(n, k) = map(int, input().split())
	a = list(map(int, input().split()))
	for i in range(1, n):
		a[i] += a[i - 1]
	c = [0 for i in range(k)]
	for i in a:
		c[i % k] += 1
	c[0] += 1
	total = 0
	for i in c:
		total += ncr(i)
	print(total)


t = int(input())
while t != 0:
	count = 0
	(n, k) = map(int, input().split())
	vi = list(map(int, input().split()))
	mod = [0] * k
	mod[0] = 1
	sum_ar = []
	sum = 0
	for i in range(len(vi)):
		sum += vi[i]
		sum_ar.append(sum)
	for i in sum_ar:
		el = i % k
		mod[el] += 1
	fin_sum = 0
	for i in mod:
		fin_sum += i * (i - 1) // 2
	print(fin_sum)
	t -= 1


t = int(input())
while t > 0:
	count = 0
	(n, k) = map(int, input().split())
	arr = list(map(int, input().split()))
	mod = [0] * k
	mod[0] = 1
	s = 0
	for i in arr:
		s += i
		mod[s % k] += 1
	s = 0
	for i in mod:
		s += i * (i - 1) // 2
	print(s)
	t -= 1


T = int(input())
while T > 0:
	S = input().strip().split(' ')
	n = int(S[0])
	k = int(S[1])
	arr = [0] * n
	S1 = input().split(' ')
	for i in range(len(S1)):
		arr[i] = int(S1[i])
		arr1 = [0] * k
		arr1[0] = 1
		arr1[arr[0] % k] += 1
		arr2 = [0] * 1
		arr2[0] = arr[0] % k
	for i in range(1, n):
		q = arr2[0]
		q1 = q + arr[i]
		arr1[q1 % k] += 1
		arr2[0] = q1 % k
	Sum = 0
	for i in range(0, k):
		Sum += arr1[i] * (arr1[i] - 1) // 2
	print(Sum)
	T -= 1


from collections import Counter
t = int(input())
for i in range(t):
	(n, k) = map(int, input().split())
	li = list(map(int, input().split()))
	arr = [0] * k
	arr[0] = 1
	ans = 0
	sum = 0
	if li[0] % k == 0:
		arr[li[0] % k] += 1
		sum = 0
	else:
		sum = li[0] % k
		arr[li[0] % k] += 1
	for i in range(1, n):
		calc = (sum + li[i]) % k
		if calc == 0:
			arr[calc] += 1
			sum = 0
		else:
			arr[calc] += 1
			sum = calc
	for i in arr:
		ans += i * (i - 1) // 2
	print(ans)


from itertools import accumulate
for i in range(int(input())):
	(n, x) = map(int, input().split())
	l = list(map(int, input().split()))
	s = list(accumulate(l))
	d = [0] * x
	d[0] = 1
	for i in s:
		d[i % x] += 1
	seq = 0
	for i in range(len(d)):
		a = d[i]
		seq += a * (a - 1) // 2
	print(seq)


def solve(a, k):
	pref = []
	for i in range(0, k):
		pref.append(0)
	pref[0] = 1
	s = 0
	for i in range(0, len(a)):
		s += a[i]
		s %= k
		pref[s] += 1
	ctr = 0
	for m in range(0, k):
		ctr += pref[m] * (pref[m] - 1) // 2
	return ctr
t = int(input())
a = []
for _ in range(t):
	(n, k) = list(map(int, input().split()))
	res = list(map(int, input().split()))
	a.append(solve(res, k))
for i in a:
	print(i)


count = int(input())
for i in range(count):
	(n, k) = map(int, input().split(' '))
	inp = map(int, input().split(' '))
	rem = []
	for i in range(k):
		rem.append(0)
	rem[0] = 1
	pres = 0
	for num in inp:
		pres += num
		pres = pres % k
		rem[pres] += 1
	sol = 0
	for r in rem:
		if r < 2:
			continue
		sol += r * (r - 1) // 2
	print(sol)


from itertools import accumulate
for _ in range(int(input())):
	(n, k) = list(map(int, input().rstrip().split()))
	l = list(map(int, input().rstrip().split()))
	s = [0] * k
	s[0] = 1
	a = list(accumulate(l))
	for i in range(len(a)):
		c = a[i] % k
		s[c] += 1
	q = 0
	for i in range(len(s)):
		res = s[i] * (s[i] - 1) / 2
		q += res
	print(int(q))


from itertools import accumulate
t = int(input())
for i in range(0, t):
	(n, k) = list(map(int, input().rstrip().split()))
	l = list(map(int, input().rstrip().split()))
	p = [0] * k
	p[0] = 1
	b = list(accumulate(l))
	for i in range(len(b)):
		s = b[i] % k
		p[s] += 1
	d = 0
	for i in range(0, len(p)):
		d = d + p[i] * (p[i] - 1) / 2
	print(int(d))


from collections import defaultdict

def countSubsequences(arr, k):
	alist = [0] * (len(arr) + 1)
	d = defaultdict(int)
	for i in range(len(arr)):
		alist[i + 1] = alist[i] + arr[i]
	subcnt = 0
	for s in alist[1:]:
		c = 0
		if s % k == 0:
			c = 1 + d[0]
			d[0] += 1
		else:
			c = d[s % k]
			d[s % k] += 1
		subcnt += c
	return subcnt
t = int(input())
for _ in range(t):
	(_, k) = input().split()
	arr = list(map(int, input().rstrip().split()))
	result = countSubsequences(arr, int(k))
	print(str(result))


for _ in range(int(input())):
	(n, k) = map(int, input().split())
	a = list(map(int, input().split()))
	c = []
	c.append(0)
	s = 0
	for i in range(0, len(a)):
		s += a[i]
		c.append(s)
	rem = [0] * k
	for i in c:
		rem[i % k] += 1
	su = 0
	for i in rem:
		su += i * (i - 1) // 2
	print(su)


n = int(input())
for i in range(n):
	(l, k) = map(int, input().split())
	arr = list(input().split())
	mod = [0] * (k + 1)
	cs = 0
	c = 0
	for i in range(l):
		cs += int(arr[i])
		mod[cs % k] += 1
	for i in range(k):
		if mod[i] > 1:
			c += mod[i] * (mod[i] - 1) // 2
	c += mod[0]
	print(c)


import sys

def count_k_subseq(k, nums):
	cumsum = [0] * len(nums)
	cumsum[0] = nums[0]
	for i in range(1, len(nums)):
		cumsum[i] = cumsum[i - 1] + nums[i]
	remainder_count = [0] * k
	for i in cumsum:
		remainder_count[i % k] += 1
	count = remainder_count[0]
	for i in remainder_count:
		count += i * (i - 1) // 2
	return count
T = int(sys.stdin.readline().strip())
for _ in range(T):
	(n, k) = sys.stdin.readline().strip().split()
	n = int(n)
	k = int(k)
	nums = sys.stdin.readline().strip().split()
	nums = [int(x) for x in nums]
	print(count_k_subseq(k, nums))


ntest = int(input())
while ntest:
	(n, k) = map(int, input().split())
	a = list(map(int, input().split()))
	(cur, du, ans) = (0, [0] * k, 0)
	du[0] = 1
	for i in range(n):
		cur += a[i]
		cur %= k
		ans += du[cur]
		du[cur] += 1
	print(ans)
	ntest -= 1


import os, sys, math

def consecutiveSubsequences(n, k, a):
	b = [0] * n
	counts = [0] * k
	b[0] = a[0] % k
	for i in range(1, n):
		b[i] = (b[i - 1] + a[i]) % k
	for x in b:
		counts[x] += 1
	s = 0
	s += counts[0]
	for (x, c) in enumerate(counts):
		if c > 0:
			s += (c * c - c) // 2
	return s

def main():
	t = int(sys.stdin.readline())
	for _ in range(t):
		(n, k) = list(map(int, sys.stdin.readline().split()))
		a = list(map(int, sys.stdin.readline().split()))
		print(consecutiveSubsequences(n, k, a))
main()


import os
import sys

def solve(nombre, n, k):
	prefixModCount = [0] * k
	prefixModCount[0] = 1
	prefixSum = 0
	for ni in nombre:
		prefixSum += ni
		prefixSum %= k
		prefixModCount[prefixSum] += 1
	resul = 0
	for mod in prefixModCount:
		resul += mod * (mod - 1) // 2
	return resul
t = int(input())
for t_itr in range(t):
	(n, k) = list(map(int, input().split()))
	nombre = list(map(int, input().split()))
	print(solve(nombre, n, k))


import sys

def solve(arr, k):
	rems = k * [0]
	result = 0
	offset = 0
	for ai in (_ % k for _ in arr):
		offset = offset - ai
		if offset < 0:
			offset += k
		rems[offset + ai - k] += 1
		result += rems[offset]
	return result
T = int(input())
for trial in range(T):
	(n, k) = [int(s) for s in input().split()]
	arr = [int(s) for s in input().split()]
	result = solve(arr, k)
	print(result)


from collections import defaultdict
T = int(input())

def solve(ns, k):
	n = len(ns)
	d = defaultdict(int)
	d[0] += 1
	pre = 0
	tot = 0
	for (i, num) in enumerate(ns):
		pre += num
		pre %= k
		tot += d[pre]
		d[pre] += 1
	return tot
for case_ in range(T):
	(n, k) = map(int, input().split())
	ns = list(map(int, input().split()))
	print(solve(ns, k))


from collections import defaultdict

def divisible_subsequences(k, v):
	remainders = defaultdict(int)
	s = 0
	remainders[0] = 1
	for x in v:
		s = (s + x) % k
		remainders[s] += 1
	return sum([r * (r - 1) // 2 for r in remainders.values()])
for _ in range(int(input())):
	(n, k) = [int(x) for x in input().split()]
	v = [int(x) for x in input().split()]
	assert n == len(v)
	print(divisible_subsequences(k, v))


def func(n, k, arr):
	total = ans = 0
	lst = [1] + [0] * (k - 1)
	for i in arr:
		total += i
		total %= k
		lst[total] += 1
	for j in lst:
		ans += j * (j - 1)
	return ans // 2
t = int(input().rstrip())
for _ in range(t):
	nk = list(map(int, input().rstrip().split()))
	n = nk[0]
	k = nk[1]
	arr = list(map(int, input().rstrip().split()))
	result = func(n, k, arr)
	print(result)


t = int(input())
for i in range(t):
	(n, k) = map(int, input().split())
	a = map(int, input().split())
	d = [0] * 111
	total = 0
	count = 0
	for i in a:
		total += i
		total %= k
		d[total] += 1
	d[0] += 1
	for i in d:
		count += i * (i - 1) // 2
	print(count)


import math

class var:
	s = 0
	ans = 0

def count(a, n, k):
	pre = [0 for _ in range(n)]
	pre[0] = a[0]
	for i in range(1, n):
		pre[i] = a[i] + pre[i - 1]
	c = [0 for _ in range(111)]
	c[0] = 1
	for i in range(n):
		c[pre[i] % k] += 1
	sum = 0
	for i in range(111):
		sum += c[i] * (c[i] - 1) / 2
	print(int(sum))
for _ in range(int(input())):
	(n, k) = map(int, input().split())
	arr = list(map(int, input().split()))
	count(arr, n, k)


import itertools
import operator
tc = int(input())
for _ in range(tc):
	(n, k) = map(int, input().split())
	a = list(map(int, input().split()))
	arr = list(itertools.accumulate(a, operator.add))
	rem_count = {}
	count = 0
	for i in range(k):
		rem_count[i] = 0
	for i in arr:
		mod = i % k
		if mod == 0:
			count += 1
		count += rem_count[mod]
		rem_count[mod] += 1
	print(count)


t = int(input())
for i in range(t):
	(n, k) = map(int, input().split())
	l = [int(x) for x in input().split()]
	s = [0]
	for j in range(n):
		s.append(s[j] + l[j])
		s[j + 1] %= k
	num = 0
	for i in range(k):
		p = s.count(i)
		if i == 0:
			num += p * (p - 1) // 2
		else:
			num += p * (p - 1) // 2
	print(num)


t = int(input())
for _ in range(t):
	(n, k) = map(int, input().split())
	ar = list(map(int, input().split()))
	for i in range(1, n):
		ar[i] += ar[i - 1]
	for i in range(n):
		ar[i] = ar[i] % k
	l = [0] * k
	for i in ar:
		l[i] += 1
	z = l[0]
	su = 0
	for i in l:
		su += i * (i - 1) // 2
	print(su + z)


from math import factorial
t = int(input())
for _ in range(t):
	(n, k) = map(int, input().split())
	li = list(map(int, input().split()))
	l1 = []
	c = 0
	for i in li:
		p = i + c
		l1.append(p % k)
		c = p
	l2 = []
	for i in range(k):
		l2.append(l1.count(i))
	p = 0
	for i in l2:
		if i < 2:
			pass
		else:
			q = factorial(i) // (factorial(i - 2) * factorial(2))
			p += q
	p += l2[0]
	print(p)


for _ in range(int(input())):
	(n, k) = map(int, input().split())
	l = list(map(int, input().split()))
	c = 0
	t = [l[0]]
	for i in range(1, n):
		t.append(t[i - 1] + l[i])
	mod = [0 for i in range(k)]
	for x in t:
		m = x % k
		if m == 0:
			c += 1
		c += mod[m]
		mod[m] += 1
	print(c)


n = int(input())
while n:
	n -= 1
	(x, k) = map(int, input().split())
	a = list(map(int, input().split()))
	m = [0] * k
	c = 0
	for i in range(x):
		c = c + a[i]
		m[c % k] = m[c % k] + 1
	c = 0
	for i in range(k):
		c = c + m[i] * (m[i] - 1) // 2
	print(c + m[0])


def subCount(arr, n, k):
	csum = 0
	mod = [0] * k
	for i in range(n):
		csum += arr[i]
		mod[(csum % k + k) % k] = mod[(csum % k + k) % k] + 1
	ans = 0
	for i in range(k):
		if mod[i] > 1:
			ans += mod[i] * (mod[i] - 1) // 2
	print(ans + mod[0])
for _ in range(int(input())):
	a = list(map(int, input().split()))
	l = list(map(int, input().split()))
	subCount(l, a[0], a[1])


from collections import Counter
for _ in range(int(input())):
	(n, k) = map(int, input().split())
	aa = list(map(int, input().split()))
	cs = [0]
	for a in aa:
		cs.append((cs[-1] + a) % k)
	sc = Counter(cs)
	print(sum((c * (c - 1) // 2 for c in sc.values())))


tc = int(input())
while tc > 0:
	(n, k) = map(int, input().split())
	p = [0] * n
	f = list(map(int, input().split()))
	p[0] = f[0]
	for i in range(1, n):
		p[i] = f[i] + p[i - 1]
	count = [0] * 111
	count[0] = 1
	for j in range(n):
		count[p[j] % k] += 1
	sum = 0
	for k in range(111):
		sum += count[k] * (count[k] - 1) / 2
	print(int(sum))
	tc -= 1


from collections import deque
cases = int(input())
for _ in range(cases):
	(n, k) = map(int, input().strip().split())
	arr = map(int, input().strip().split())
	if k == 1:
		print(n * (n + 1) // 2)
		continue
	table = deque([0] * k)
	result = 0
	for x in arr:
		rot = x % k
		if rot > 0:
			table.rotate(rot)
		table[rot] += 1
		result += table[0]
	print(result)


import sys
from collections import defaultdict
numtests = int(input())
for tcnumber in range(numtests):
	(n, k) = input().split()
	n = int(n)
	k = int(k)
	arr = list(map(int, sys.stdin.readline().split()))
	prefsums = defaultdict(int)
	prefsums[0] = 1
	currsum = 0
	res = 0
	for i in range(n):
		currsum += arr[i]
		res += prefsums[currsum % k]
		prefsums[currsum % k] += 1
	print(res)


from collections import Counter

def solve(array, k):
	for i in range(len(array)):
		array[i] %= k
	counts = Counter()
	counts[0] += 1
	s = 0
	for x in array:
		s = (s + x) % k
		counts[s] += 1
	output = 0
	for c in counts.values():
		output += c * (c - 1) // 2
	return output

def main():
	t = int(input().rstrip())
	for i in range(t):
		(n, k) = list(map(int, input().rstrip().split()))
		array = list(map(int, input().rstrip().split()))
		result = solve(array, k)
		print(result)
main()


t = int(input())
for _ in range(t):
	inp = list(map(int, input().split()))
	n = inp[0]
	k = inp[1]
	inp = list(map(int, input().split()))
	ans = 0
	s = 0
	from collections import Counter
	arr = []
	for item in inp:
		s += item
		arr.append(s % k)
	c = Counter([])
	for i in range(len(arr)):
		if arr[i] == 0:
			ans += 1
		if c[arr[i]] != 0:
			ans += c[arr[i]]
		c[arr[i]] += 1
	print(ans)


def no_conseq_sub(x, k):
	tot = 0
	cumulative = []
	no_mod = [0 for _ in range(k)]
	no_mod[0] = 1
	no_sub = 0
	for i in x:
		tot += i % k
		tot %= k
		no_mod[tot] += 1
		cumulative.append(tot)
	for i in no_mod:
		no_sub += int(i * (i - 1) / 2)
	return no_sub
no_test = int(input())
for _ in range(no_test):
	(n, k) = map(int, input().split(' '))
	N = list(map(int, input().split(' ')))
	print(no_conseq_sub(N, k))


def kSub(k, nums):
	temp = [0 for _ in range(k + 1)]
	running = 0
	for i in range(n):
		running = running + nums[i]
		index = (running % k + k) % k
		temp[index] += 1
	result = 0
	for i in range(k):
		if temp[i] > 1:
			result += temp[i] * (temp[i] - 1) // 2
	result = result + temp[0]
	return result
t = int(input())
for _ in range(t):
	(n, k) = map(int, input().split())
	nums = list(map(int, input().split()))
	print(kSub(k, nums))


from itertools import accumulate
t = int(input())
for _ in range(t):
	res = 0
	(n, k) = map(int, input().split())
	a = list(map(int, input().split()))
	mod = [0] * k
	s = 0
	for i in range(n):
		s += a[i]
		mod[(s % k + k) % k] += 1
	for j in range(k):
		if mod[j] > 1:
			res += mod[j] * (mod[j] - 1) // 2
	res += mod[0]
	print(res)


T = int(input())
for _ in range(T):
	(n, k) = list(map(int, input().split(' ')))
	ar = list(map(int, input().split(' ')))
	count = 0
	prefixModCount = [0] * k
	prefixModCount[0] = 1
	prefixSum = 0
	for i in range(n):
		prefixSum += ar[i]
		prefixSum %= k
		prefixModCount[prefixSum] += 1
	for mod in range(k):
		count += prefixModCount[mod] * (prefixModCount[mod] - 1) / 2
	print(int(count))


for _ in range(int(input())):
	(n, k) = map(int, input().split())
	l = list(map(int, input().split()))
	l1 = [l[0]]
	c = [0] * 100
	d = 0
	for i in range(1, len(l)):
		l1.append(l[i] + l1[i - 1])
	for i in range(len(l1)):
		c[l1[i] % k] += 1
	for i in range(len(c)):
		if i == 0:
			d += c[i] * (c[i] + 1) // 2
		else:
			d += c[i] * (c[i] - 1) // 2
	print(d)


t = int(input())
for i in range(t):
	L = list(map(int, input().split()))
	n = L[0]
	k = L[1]
	L = list(map(int, input().split()))
	F = []
	for j in range(k):
		F.append(0)
	F[0] = 1
	s = 0
	for j in range(n):
		s += L[j]
		F[s % k] += 1
	s = 0
	for j in range(k):
		s += F[j] * (F[j] - 1) / 2
	print(int(s))


t = int(input())
for _ in range(t):
	(n, k) = map(int, input().split())
	a = list(map(int, input().split()))
	cnt_mod = [0] * k
	cnt_mod[0] = 1
	prefix = 0
	res = 0
	for ai in a:
		prefix = (prefix + ai) % k
		res += cnt_mod[prefix]
		cnt_mod[prefix] += 1
	print(res)


t = int(input())
while t > 0:
	(n, k) = [int(x) for x in input().split(' ')]
	a = [int(x) for x in input().split(' ')]
	count = 0
	m = [0] * k
	for i in a:
		i = i % k
		ni = (k - i) % k
		m = m[ni:] + m[:ni]
		m[i] += 1
		count += m[0]
	print(count)
	t -= 1


from sys import stdin
t = int(stdin.readline())
for _ in range(t):
	(n, k) = map(int, stdin.readline().split())
	arr = list(map(int, stdin.readline().split()))
	di = {}
	sumi = 0
	tot = 0
	vis = {}
	for i in range(n):
		sumi = (sumi + arr[i] % k) % k
		if sumi == 0:
			vis[arr[i]] = 0
			tot += 1
		if sumi in di:
			di[sumi] += 1
		else:
			di[sumi] = 1
	for i in di:
		if di[i] > 1:
			tot += di[i] * (di[i] - 1) // 2
	print(tot)