A batch of $n$ goods ($n$ — an even number) is brought to the store, $i$-th of which has weight $a_i$. Before selling the goods, they must be packed into packages. After packing, the following will be done:

There will be $\frac{n}{2}$ packages, each package contains exactly two goods;

The weight of the package that contains goods with indices $i$ and $j$ ($1 \le i, j \le n$) is $a_i + a_j$.

With this, the cost of a package of weight $x$ is always $\left \lfloor\frac{x}{k}\right\rfloor$ burles (rounded down), where $k$ — a fixed and given value.

Pack the goods to the packages so that the revenue from their sale is maximized. In other words, make such $\frac{n}{2}$ pairs of given goods that the sum of the values $\left \lfloor\frac{x_i}{k} \right \rfloor$, where $x_i$ is the weight of the package number $i$ ($1 \le i \le \frac{n}{2}$), is maximal.

For example, let $n = 6, k = 3$, weights of goods $a = [3, 2, 7, 1, 4, 8]$. Let's pack them into the following packages.

In the first package we will put the third and sixth goods. Its weight will be $a_3 + a_6 = 7 + 8 = 15$. The cost of the package will be $\left \lfloor\frac{15}{3}\right\rfloor = 5$ burles.

In the second package put the first and fifth goods, the weight is $a_1 + a_5 = 3 + 4 = 7$. The cost of the package is $\left \lfloor\frac{7}{3}\right\rfloor = 2$ burles.

In the third package put the second and fourth goods, the weight is $a_2 + a_4 = 2 + 1 = 3$. The cost of the package is $\left \lfloor\frac{3}{3}\right\rfloor = 1$ burle.

With this packing, the total cost of all packs would be $5 + 2 + 1 = 8$ burles.


-----Input-----

The first line of the input contains an integer $t$ ($1 \le t \le 10^4$) —the number of test cases in the test.

The descriptions of the test cases follow.

The first line of each test case contains two integers $n$ ($2 \le n \le 2\cdot10^5$) and $k$ ($1 \le k \le 1000$). The number $n$ — is even.

The second line of each test case contains exactly $n$ integers $a_1, a_2, \dots, a_n$ ($0 \le a_i \le 10^9$).

It is guaranteed that the sum of $n$ over all the test cases does not exceed $2\cdot10^5$.


-----Output-----

For each test case, print on a separate line a single number — the maximum possible total cost of all the packages.


-----Examples-----

Input
6
6 3
3 2 7 1 4 8
4 3
2 1 5 6
4 12
0 0 0 0
2 1
1 1
6 10
2 0 0 5 9 4
6 5
5 3 8 6 3 2
Output
8
4
0
2
1
5


-----Note-----

The first test case is analyzed in the statement.

In the second test case, you can get a total value equal to $4$ if you put the first and second goods in the first package and the third and fourth goods in the second package.

In the third test case, the cost of each item is $0$, so the total cost will also be $0$.

Source: codeforces | Difficulty: MEDIUM
Tags: Sorting

Amortized analysis

Mathematics

Greedy algorithms


Solutions:
def main():
	for _ in range(int(input())):
		problem()

def problem():
	(n, k) = map(int, input().split())
	weights = list(map(int, input().split()))
	cost = sum((w // k for w in weights))
	weights = [w % k for w in weights]
	weights.sort()
	(i, j) = (0, n - 1)
	while i < j:
		if weights[i] + weights[j] >= k:
			cost += 1
			i += 1
			j -= 1
		else:
			i += 1
	print(cost)
import sys
input = sys.stdin.readline
exit(main())


from sys import stdin, stdout, setrecursionlimit
import collections
import math
from collections import deque

def test():
	return

def solve():
	return

def main():
	for _ in range(int(input())):
		(n, k) = map(int, input().split())
		l = list(map(int, input().split()))
		ans = 0
		d = []
		for i in l:
			ans += i // k
			d.append(i % k)
		d.sort()
		l = n - 1
		for i in range(n):
			if i < l:
				if (d[i] + d[l]) // k >= 1:
					ans += (d[i] + d[l]) // k
					l -= 1
		print(ans)
	return
input = stdin.readline
main()


from random import getrandbits
RANDOM = getrandbits(32)

class Wrapper(int):

	def __init__(self, x):
		int.__init__(x)

	def __hash__(self):
		return super(Wrapper, self).__hash__() ^ RANDOM
T = int(input())
q = []
for i in range(T):
	a = input().split()
	(n, k) = (int(a[0]), int(a[1]))
	data = [int(i) for i in input().split()]
	q.append((n, k, data))

def solve(n, k, data):
	pay = 0
	lefts = []
	for d in data:
		pay += d // k
		lefts.append(d % k)
	lefts = sorted(lefts)
	l = 0
	r = n - 1
	while l < r:
		if lefts[l] + lefts[r] >= k:
			l += 1
			r -= 1
			pay += 1
		else:
			l += 2
	print(pay)
for (n, k, data) in q:
	solve(n, k, data)


from sys import stdin
from bisect import bisect_left as bl
input = stdin.readline
for test in range(int(input())):
	(n, k) = map(int, input().split())
	package = list(map(int, input().split()))
	rem = sorted((i % k for i in package))
	package = [i // k for i in package]
	s = sum(package)
	left = bl(rem, 1)
	for right in range(n - 1, -1, -1):
		while left < right and rem[left] + rem[right] < k:
			left += 1
		if left < right:
			s += 1
		else:
			break
		left += 1
	print(s)


import sys
import collections
from math import ceil, gcd, sqrt, log
import bisect
INF = float('inf')
mod = 1000000007

def solve():
	(n, k) = map(int, input().split())
	A = list(map(int, input().split()))
	ans = 0
	for i in range(n):
		ans += A[i] // k
		A[i] = A[i] % k
	A.sort()
	(i, j) = (0, n - 1)
	while i < j:
		net = A[i] + A[j]
		if net < k:
			i += 1
		else:
			ans += 1
			i += 1
			j -= 1
	print(ans)
t = int(input())
while t != 0:
	solve()
	t -= 1


for _ in range(int(input())):
	(n, k) = map(int, input().split(' '))
	a = list(map(int, input().split(' ')))
	ans = sum((_ // k for _ in a))
	m = [_ % k for _ in a]
	m.sort()
	(x, y) = (0, n - 1)
	while x < y:
		if m[x] + m[y] >= k:
			ans += 1
			x += 1
			y -= 1
		else:
			x += 1
	print(ans)


def solve(arr, k):
	res = 0
	for i in range(len(arr)):
		res += arr[i] // k
		arr[i] %= k
	arr.sort()
	left = 0
	right = len(arr) - 1
	while right > left:
		if arr[right] + arr[left] >= k:
			res += 1
			right -= 1
			left += 1
		else:
			left += 1
	return res
t = int(input())
for _ in range(t):
	(n, k) = map(int, input().split())
	arr = list(map(int, input().split()))
	res = solve(arr, k)
	print(res)


def res(n, k, a):
	ans = 0
	for i in range(n):
		ans += a[i] // k
		a[i] %= k
	a.sort()
	i = 0
	j = n - 1
	while i < j:
		if a[i] + a[j] >= k:
			ans += 1
			j -= 1
		i += 1
	return ans
t = int(input())
for _ in range(t):
	(n, k) = map(int, input().split())
	a = [int(x) for x in input().split()]
	print(res(n, k, a))


def solve():
	(n, k) = map(int, input().split())
	a = list(map(int, input().split()))
	ans = 0
	for i in range(n):
		ans += a[i] // k
		a[i] %= k
	a.sort()
	(l, r) = (0, n - 1)
	while l < r:
		if a[l] + a[r] < k:
			l += 1
			continue
		ans += 1
		l += 1
		r -= 1
	print(ans)
T = int(input())
for _ in range(T):
	solve()


from sys import stdin
input = stdin.readline
for _ in range(int(input())):
	(n, k) = map(int, input().split(' '))
	a = list(map(int, input().split(' ')))
	ans = sum((_ // k for _ in a))
	m = [_ % k for _ in a]
	m.sort()
	(x, y) = (0, n - 1)
	while x < y:
		if m[x] + m[y] >= k:
			ans += 1
			x += 1
			y -= 1
		else:
			x += 1
	print(ans)


from sys import stdin
input = stdin.readline
for _ in range(int(input())):
	(n, k) = map(int, input().split(' '))
	i = 0
	a = [None] * n
	m = [None] * n
	for c in input().split(' '):
		t = int(c)
		a[i] = t // k
		m[i] = t % k
		i += 1
	ans = sum(a)
	m.sort()
	(x, y) = (0, n - 1)
	while x < y:
		if m[x] + m[y] >= k:
			ans += 1
			x += 1
			y -= 1
		else:
			x += 1
	print(ans)


tc = int(input())
for t in range(tc):
	(n, k) = map(int, input().split())
	arr = list(map(int, input().split()))
	cost = sum((w // k for w in arr))
	weights = [w % k for w in arr]
	weights.sort()
	weights.sort()
	(i, j) = (0, n - 1)
	while i < j:
		if weights[i] + weights[j] >= k:
			cost += 1
			i += 1
			j -= 1
		else:
			i += 1
	print(cost)


x = int(input())

def cal(n, m, s):
	res = 0
	for i in range(n):
		res += s[i] // m
		s[i] = s[i] % m
	(i, j) = (0, n - 1)
	s.sort()
	while i < j:
		if s[i] + s[j] < m:
			i += 1
			continue
		else:
			res += 1
			i += 1
			j -= 1
	return res
for jj in range(x):
	(n, m) = [int(i) for i in input().split(' ')]
	arr = [int(i) for i in input().split(' ')]
	print(cal(n, m, arr))


from collections import deque

def solve():
	(n, k) = map(int, input().split())
	A = list(map(int, input().split()))
	ans = 0
	M = []
	for a in A:
		ans += a // k
		M.append(a % k)
	M.sort()
	que = deque()
	for m in M:
		if que and que[-1] + m >= k:
			ans += 1
			que.pop()
		else:
			que.append(m)
	print(ans)
for _ in range(int(input())):
	solve()


def f():
	nk = list(map(int, input().split()))
	n = nk[0]
	k = nk[1]
	a = list(map(int, input().split()))
	start = 0
	end = n - 1
	a = sorted(a, key=lambda x: x % k)
	b = [x % k for x in a]
	result = 0
	while start < end:
		if b[end] + b[start] >= k:
			result += (a[start] + a[end]) // k
			end -= 1
			start += 1
		else:
			result += a[start] // k
			start += 1
	if start == end:
		result += a[start] // k
	return result
t = input()
for i in range(int(t)):
	print(f())


import sys
import collections
import bisect
import math
from functools import lru_cache
for _ in range(int(input())):
	(n, k) = list(map(int, sys.stdin.readline().split()))
	arr = list(map(int, sys.stdin.readline().split()))
	res = 0
	for i in range(n):
		res += arr[i] // k
		arr[i] = arr[i] % k
	arr.sort()
	j = n - 1
	for i in range(n):
		if j > i and arr[i] + arr[j] >= k:
			res += 1
			j -= 1
		if i >= j:
			break
	print(res)


import sys
import threading
from collections import defaultdict
from collections import Counter
from string import ascii_lowercase
from functools import lru_cache
from collections import deque
import heapq

def inp():
	return int(input())

def inlt():
	return list(map(int, input().split()))

def insr():
	s = input()
	return list(s[:len(s) - 1])

def invr():
	return map(int, input().split())

def main():
	cases = inp()
	for case in range(cases):
		(leng, k) = inlt()
		arr = inlt()
		total = 0
		for index in range(len(arr)):
			total += arr[index] // k
			arr[index] = arr[index] % k
		arr.sort()
		(left, right) = (0, len(arr) - 1)
		while left < right:
			while left < right and arr[left] + arr[right] < k:
				left += 1
			if left < right:
				total += 1
				right -= 1
				left += 1
		print(total)
main()


from collections import deque

def solve():
	(n, k) = map(int, input().split())
	inp = [int(i) for i in input().split()]
	res = 0
	for (i, v) in enumerate(inp):
		res += v // k
		inp[i] %= k
	inp.sort(reverse=True)
	q = deque(inp)
	while q:
		a = q.popleft()
		while q:
			b = q.pop()
			if a + b >= k:
				res += 1
				break
	return res

def main():
	for _ in range(int(input())):
		print(solve())
	return
main()


for _ in range(int(input())):
	(n, k) = map(int, input().split())
	a = list(map(int, input().split()))
	b = [x % k for x in a]
	b.sort()
	s = sum(a)
	i = 0
	j = n - 1
	while i < j:
		if b[i] + b[j] >= k:
			s -= b[i] + b[j] - k
			j -= 1
		else:
			s -= b[i]
		i += 1
	if i == j:
		s -= b[i]
	print(int(s / k))


li = lambda : list(map(int, input().split()))
lis = lambda : sorted(list(map(int, input().split())))
mp = lambda : map(int, input().split())
it = lambda : int(input())
st = lambda : str(input())
from collections import Counter

def twopointers(A, N, X):
	i = 0
	j = N - 1
	while i < j:
		if A[i] + A[j] == X:
			return True
		elif A[i] + A[j] < X:
			i += 1
		else:
			j -= 1
	return 0

def shortest_path(k, n, neighbors):
	mark = [-1] * (n + 1)
	mark[k] = 0
	bfs_queue = [k]
	i = 0
	while i < len(bfs_queue):
		u = bfs_queue[i]
		for v in neighbors[u]:
			if mark[v] == -1:
				mark[v] = mark[u] + 1
				bfs_queue.append(v)
		i += 1
	return mark
import math

def main():
	(a, b) = mp()
	c = li()
	ans = 0
	ccc = []
	for i in range(a):
		ans += c[i] // b
		ccc.append(c[i] % b)
	ccc.sort()
	l = 0
	r = a - 1
	while l < r:
		if ccc[l] + ccc[r] >= b:
			ans += (ccc[l] + ccc[r]) // b
			r -= 1
			l += 1
		else:
			l += 1
	print(ans)
for __ in range(it()):
	main()


def solve():
	(n, k) = map(int, input().split())
	a = list(map(int, input().split()))
	t = []
	ans = 0
	for i in range(n):
		ans += a[i] // k
		if a[i] % k:
			t.append(a[i] % k)
	t.sort()
	l = 0
	r = len(t) - 1
	while l < r:
		if t[l] + t[r] >= k:
			ans += 1
			l += 1
			r -= 1
		else:
			l += 1
	print(ans)
t = int(input())
for i in range(t):
	solve()


for test in range(int(input())):
	(n, k) = map(int, input().split())
	a = list(map(int, input().split()))
	ans = 0
	for i in a:
		ans += i // k
	remainders = [i % k for i in a]
	remainders.sort()
	(p1, p2) = (0, n - 1)
	while p1 < p2:
		if remainders[p1] + remainders[p2] >= k:
			ans += 1
			p1 += 1
			p2 -= 1
		elif remainders[p1] + remainders[p2] < k:
			p1 += 1
	print(ans)


R = lambda : map(int, input().split())
(t,) = R()
while t:
	t -= 1
	(n, k) = R()
	r = 0
	a = []
	for x in R():
		r += x // k
		a += (x % k,)
	a.sort()
	i = 0
	n -= 1
	while i < n:
		if a[i] + a[n] >= k:
			r += 1
			n -= 1
		i += 1
	print(r)


class PriceMaximization:

	def maximize(self, n, k, a):
		result = 0
		remainderList = []
		for i in a:
			result += i // k
			l = i % k
			if l:
				remainderList.append(l)
		remainderList.sort()
		n1 = len(remainderList)
		leftPointer = 0
		rightPointer = n1 - 1
		while leftPointer < rightPointer:
			if remainderList[leftPointer] + remainderList[rightPointer] >= k:
				result += 1
				leftPointer += 1
				rightPointer -= 1
			else:
				leftPointer += 1
		print(result)
		return
T = int(input())
while T:
	T -= 1
	(n, k) = map(int, input().split())
	a = list(map(int, input().split()))
	PriceMaximization().maximize(n, k, a)


for _ in range(int(input())):
	(n, k) = [int(x) for x in input().split()]
	a = [int(x) for x in input().split()]
	amodk = sorted((a[i] % k for i in range(n)))
	summ = sum((a[i] // k for i in range(n)))
	p = 0
	i = n - 1
	while p < i:
		biggest = amodk[i]
		while p < i and amodk[p] + biggest < k:
			p += 1
		if p < i:
			summ += 1
		i -= 1
		p += 1
	print(summ)


test_case = int(input())
for _ in range(test_case):
	(n, k) = map(int, input().split())
	a = list(map(int, input().split()))
	ans = sum([a[i] // k for i in range(n)])
	a = sorted(list(map(lambda x: x % k, a)))
	i = 0
	j = n - 1
	while i < j:
		while i < j and a[i] + a[j] < k:
			i += 1
		if i < j:
			ans += 1
		i += 1
		j -= 1
	print(ans)


for test in range(int(input())):
	(n, k) = map(int, input().split())
	a = [int(i) for i in input().split()]
	res = 0
	rem = []
	for i in a:
		res += i // k
		rem.append(i % k)
	rem.sort()
	(l, r) = (0, n - 1)
	while r > l:
		if rem[l] + rem[r] >= k:
			res += 1
			r -= 1
		l += 1
	print(res)


for _ in range(int(input())):
	(n, k) = map(int, input().split())
	a = list(map(int, input().split()))
	lst = []
	ans = 0
	for i in a:
		lst.append(i % k)
		ans += i // k
	lst.sort()
	i = 0
	j = len(lst) - 1
	while j > i:
		if lst[i] + lst[j] >= k:
			ans += 1
			j -= 1
		i += 1
	print(ans)


for _ in range(int(input())):
	(n, k) = list(map(int, input().split()))
	a = list(map(int, input().split()))
	sumA = sum([num // k for num in a])
	mod = [num % k for num in a]
	mod.sort()
	bonus = 0
	(s, e) = (0, n - 1)
	while s < e:
		if mod[s] + mod[e] >= k:
			bonus += 1
			s += 1
			e -= 1
		else:
			s += 1
	print(sumA + bonus)


from cmath import sqrt
from collections import defaultdict
import heapq
from math import *
import sys
from tkinter import N
from typing import Counter
input = sys.stdin.readline
for _ in range(int(input())):
	(n, k) = list(map(int, input().split()))
	a = list(map(int, input().split()))
	b = []
	ans = 0
	for i in range(n):
		ans += a[i] // k
		b.append(a[i] % k)
	i = 0
	j = n - 1
	b.sort()
	while i < j:
		if b[i] + b[j] >= k:
			ans += 1
			i += 1
			j -= 1
		else:
			i += 1
	print(ans)


for _ in range(int(input())):
	(a, k) = map(int, input().split())
	c = [*map(int, input().split())]
	ans = 0
	for i in range(a):
		ans += c[i] // k
		c[i] = c[i] % k
	c.sort()
	(l, r) = (0, a - 1)
	while l < r:
		if c[l] + c[r] >= k:
			ans += 1
			l += 1
			r -= 1
		else:
			l += 1
	print(ans)


for x in range(int(input())):
	(n, k) = map(int, input().split())
	a = list(map(int, input().split()))
	s = 0
	for x in range(len(a)):
		s += a[x] // k
		a[x] = a[x] % k
	a.sort()
	i = 0
	j = n - 1
	while i < j:
		if a[i] + a[j] >= k:
			s += 1
			j -= 1
		i += 1
	print(s)


e = lambda : map(int, input().split())
(t,) = e()
while t:
	t -= 1
	(n, k) = e()
	i = 1
	j = n
	a = [0]
	for x in e():
		n += x // k
		a += (x % k,)
	a.sort()
	while i < j:
		j -= a[i] + a[j] >= k
		i += 1
	print(n - j)


from collections import deque
N = int(input())
for _ in range(N):
	(n, k) = map(int, input().split())
	arr = list(map(int, input().split()))
	summ = sum([a // k for a in arr])
	arr = deque(sorted([a % k for a in arr if a % k > 0], reverse=True))
	change = 'yes'
	while arr:
		if change == 'yes':
			a = arr.popleft()
			if not arr:
				break
		b = arr.pop()
		if b + a >= k:
			summ += 1
			change = 'yes'
		else:
			change = 'no'
	print(summ)


for _ in range(int(input())):
	(x, y) = map(int, input().split())
	a = list(map(int, input().split()))
	ans = 0
	for i in range(x):
		ans += a[i] // y
		a[i] %= y
	a.sort()
	j = x - 1
	i = 0
	while i < j:
		if a[i] + a[j] >= y:
			ans += 1
			j -= 1
		i += 1
	print(ans)


for _ in range(int(input())):
	(n, k) = map(int, input().split())
	l = list(map(int, input().split()))
	ans = 0
	for i in range(n):
		ans += l[i] // k
		l[i] = l[i] % k
	l.sort()
	i = 0
	j = n - 1
	while i < j:
		if l[i] + l[j] >= k:
			ans += 1
			j -= 1
		i += 1
	print(ans)


for _ in range(int(input())):
	(n, k) = map(int, input().split())
	a = [*map(int, input().split())]
	ans = 0
	rem = []
	for x in a:
		ans += x // k
		rem.append(x % k)
	(l, r) = (0, n - 1)
	rem.sort()
	while l < r:
		if rem[l] + rem[r] >= k:
			ans += 1
			r -= 1
		l += 1
	print(ans)


import os
import sys
import math

def solve():
	(n, k) = map(int, input().split())
	l = list(map(int, input().split()))
	ans = 0
	for i in range(0, len(l)):
		ans += l[i] // k
		l[i] %= k
	l.sort()
	i = 0
	j = len(l) - 1
	while i < j:
		if l[i] + l[j] >= k:
			i += 1
			j -= 1
			ans += 1
		else:
			i += 1
	print(ans)
if os.path.exists('D:/VSCODE/cp/input.txt'):
	sys.stdin = open('D:/VSCODE/cp/input.txt', 'r')
	sys.stdout = open('D:/VSCODE/cp/output.txt', 'w')
t = int(input())
for testcase in range(1, t + 1):
	solve()


for _ in range(int(input())):
	(n, k) = map(int, input().split())
	nums = list(map(int, input().split()))
	ans = 0
	for i in range(n):
		ans += nums[i] // k
		nums[i] = nums[i] % k
	i = 0
	j = n - 1
	nums.sort()
	while i < j:
		while i < j and nums[i] + nums[j] < k:
			i += 1
		if not i < j:
			break
		j -= 1
		i += 1
		ans += 1
	print(ans)


from math import *
import os
import random
import re
import sys
from itertools import *
m = pow(10, 9) + 7
for t in range(int(input())):
	(n, k) = map(int, input().split())
	a = list(map(int, input().split()))
	ans = 0
	for i in range(n):
		ans += a[i] // k
		a[i] %= k
	a.sort()
	i = 0
	j = n - 1
	while i < j:
		if a[i] + a[j] < k:
			i += 1
		else:
			ans += 1
			i += 1
			j -= 1
	print(ans)


for t in range(int(input())):
	(n, k) = map(int, input().split())
	a = list(map(int, input().split()))
	ans = 0
	for i in range(n):
		ans += a[i] // k
		a[i] %= k
	a.sort()
	i = 0
	j = n - 1
	while i < j:
		if a[i] + a[j] < k:
			i += 1
		else:
			ans += 1
			i += 1
			j -= 1
	print(ans)


for i in range(int(input())):
	(n, k) = [int(i) for i in input().split()]
	a = [int(i) for i in input().split()]
	b = []
	res = 0
	for i in a:
		res += i // k
		b.append(i % k)
	b = sorted(b)[::-1]
	j = n - 1
	for i in range(n):
		while b[i] + b[j] < k and i < j:
			j -= 1
		if i >= j:
			break
		res += 1
		j -= 1
	print(res)


from itertools import combinations
for _ in range(int(input())):
	(size, k) = map(int, input().split())
	arr = list(map(int, input().split()))
	ans = 0
	for i in range(size):
		ans += arr[i] // k
		arr[i] = arr[i] % k
	arr.sort()
	l = 0
	r = len(arr) - 1
	while r > l:
		if arr[r] + arr[l] >= k:
			ans += 1
			r -= 1
			l += 1
		else:
			l += 1
	print(ans)


t = int(input())
for __ in range(t):
	(n, k) = map(int, input().split())
	x1 = list(map(int, input().split()))
	s = sum(list(map(lambda x: x // k, x1)))
	M = sorted([x1[i] % k for i in range(n) if x1[i] % k != 0])
	l = 0
	r = len(M) - 1
	while l < r:
		if M[l] + M[r] >= k:
			s += 1
			r -= 1
		l += 1
	print(s)


for i in range(int(input())):
	(n, k) = map(int, input().split())
	lst = list(map(int, input().split()))
	z = 0
	for i in range(n):
		z = z + lst[i] // k
		lst[i] = lst[i] % k
	lst.sort()
	j = n - 1
	for i in range(n):
		if i >= j:
			break
		if lst[i] + lst[j] >= k:
			z = z + 1
			j = j - 1
	print(z)


t = int(input())
for q in range(t):
	(n, k) = map(int, input().split())
	l = list(map(int, input().split()))
	z = 0
	for i in range(n):
		z = z + l[i] // k
		l[i] = l[i] % k
	l.sort()
	j = n - 1
	for i in range(n):
		if i >= j:
			break
		if l[i] + l[j] >= k:
			z = z + 1
			j = j - 1
	print(z)


for _ in range(int(input())):
	(l, k) = map(int, input().split())
	nums = list(map(int, input().split()))
	(left, right) = (0, len(nums) - 1)
	ans = 0
	for i in range(l):
		ans += nums[i] // k
		nums[i] %= k
	nums.sort()
	while left < right:
		pair = nums[left] + nums[right]
		if pair >= k:
			ans += 1
			left += 1
			right -= 1
		else:
			left += 1
	print(ans)


t = int(input())
for _ in range(t):
	(n, k) = [int(x) for x in input().split()]
	arr = [int(x) for x in input().split()]
	ans = 0
	rem = []
	for i in arr:
		ans += i // k
		rem.append(i % k)
	rem.sort()
	(p, q) = (0, n - 1)
	while p < q:
		if rem[p] + rem[q] >= k:
			ans += 1
			p += 1
			q -= 1
		elif rem[p] + rem[q] < k:
			p += 1
	print(ans)


t = int(input())
while t:
	(n, k) = map(int, input().split())
	l = list(map(int, input().split()))
	lr = []
	ans = 0
	for i in range(n):
		ans += l[i] // k
		lr.append(l[i] % k)
	lr.sort()
	(le, r) = (0, n - 1)
	while le < r:
		if (lr[le] + lr[r]) // k > 0:
			ans += 1
			r -= 1
			le += 1
		else:
			le += 1
	print(ans)
	t -= 1


for _ in range(int(input())):
	(n, k) = [int(x) for x in input().split()]
	a = [int(x) for x in input().split()]
	ans = 0
	for i in range(n):
		ans += a[i] // k
		a[i] = a[i] % k
	a.sort()
	i = 0
	j = n - 1
	while j > i:
		if a[i] + a[j] >= k:
			ans += 1
			j = j - 1
			i = i + 1
		else:
			i = i + 1
	print(ans)


from collections import defaultdict
t = int(input())
while t != 0:
	(n, k) = map(int, input().split())
	list1 = list(map(int, input().split()))
	ans = 0
	for i in range(n):
		ans += list1[i] // k
		list1[i] = list1[i] % k
	list1.sort()
	i = 0
	j = n - 1
	while i < j:
		s = list1[i] + list1[j]
		if s >= k:
			ans += 1
			j -= 1
		i += 1
	print(ans)
	t -= 1


_ = int(input())
for __ in range(_):
	(n, k) = map(int, input().split())
	packs = list(map(int, input().split()))
	out = 0
	mods = []
	for x in packs:
		out += x // k
		mods.append(x % k)
	mods = sorted(mods)
	i = 0
	j = n - 1
	while i < j:
		if mods[i] + mods[j] < k:
			i += 1
		else:
			i += 1
			j -= 1
			out += 1
	print(out)


t = int(input())
for _ in range(t):
	(n, k) = [int(i) for i in input().strip().split()]
	a = [int(i) for i in input().strip().split()]
	ans = 0
	for i in range(n):
		ans += a[i] // k
		a[i] %= k
	a.sort()
	i = 0
	j = n - 1
	while i < j:
		while i < j and a[i] + a[j] < k:
			i += 1
		if i == j:
			break
		ans += 1
		i += 1
		j -= 1
	print(ans)


for _ in range(int(input())):
	(n, k) = map(int, input().split(' '))
	i = 0
	m = [None] * n
	ans = 0
	for c in input().split(' '):
		t = int(c)
		ans += t // k
		m[i] = t % k
		i += 1
	m.sort()
	(x, y) = (0, n - 1)
	while x < y:
		if m[x] + m[y] >= k:
			ans += 1
			x += 1
			y -= 1
		else:
			x += 1
	print(ans)


t = int(input())
for i in range(t):
	(n, k) = map(int, input().split())
	lst = list(map(int, input().split()))
	c = 0
	lst1 = []
	for j in lst:
		q = j // k
		r = j % k
		lst1.append(r)
		c += q
	lst1.sort()
	le = len(lst1)
	r = le - 1
	l = 0
	while l < r:
		if lst1[r] + lst1[l] >= k:
			c += 1
			l += 1
			r -= 1
		else:
			l += 1
	print(c)


N = int(input())
for ii in range(N):
	(n, k) = map(int, input().split())
	ll = list(map(int, input().split()))
	ls = [0] * n
	res = 0
	jj = 0
	for i in range(n):
		res += ll[i] // k
		ls[i] = ll[i] % k
	ls = sorted(ls, reverse=True)
	(l, r) = (0, n - 1)
	while l < r:
		if ls[l] + ls[r] < k:
			r -= 1
		else:
			jj += 1
			l += 1
			r -= 1
	print(jj + res)


for t in range(int(input())):
	(n, k) = map(int, input().split())
	a = list(map(int, input().split()))
	ans = 0
	rem = []
	for i in a:
		ans += i // k
		if i % k:
			rem.append(i % k)
	rem.sort(reverse=True)
	left = 0
	right = len(rem) - 1
	while left < right:
		if (rem[left] + rem[right]) // k == 1:
			left += 1
			right -= 1
			ans += 1
		else:
			right -= 1
	print(ans)


for _ in range(int(input())):
	(n, k) = map(int, input().split())
	a = list(map(int, input().split()))
	ans = 0
	b = list()
	for i in range(n):
		ans += a[i] // k
		b.append(a[i] % k)
	b.sort()
	i = 0
	j = n - 1
	while i < j:
		gig = b[i] + b[j]
		if gig >= k:
			j -= 1
			ans += 1
		i += 1
	print(ans)


for _ in range(int(input())):
	(n, k) = list(map(int, input().split()))
	val = list(map(int, input().split()))
	out = 0
	left = []
	for v in range(len(val)):
		out += val[v] // k
		left.append(val[v] % k)
	left = sorted(left)
	(l, r) = (0, n - 1)
	while r > l:
		if left[l] + left[r] >= k:
			out += 1
			r -= 1
		l += 1
	print(out)


t = int(input())
for tt in range(t):
	(n, k) = map(int, input().split())
	a = list(map(int, input().split()))
	ans = 0
	for i in range(n):
		ans += a[i] // k
		a[i] %= k
	a.sort()
	used = [False for i in range(n)]
	ii = -1
	jj = n - 1
	for i in range(n):
		if a[i] > 0:
			ii = i
			break
	if ii == -1:
		print(ans)
	else:
		while ii < jj:
			if a[ii] + a[jj] >= k:
				ans += 1
				jj -= 1
			ii += 1
		print(ans)


tests = int(input())
for _ in range(tests):
	(n, k) = tuple(map(int, input().split()))
	array = list(map(int, input().split()))
	quotient = 0
	remd = []
	for n in array:
		quotient += n // k
		r = n % k
		if r:
			remd.append(r)
	remd.sort()
	i = 0
	j = len(remd) - 1
	while i < j:
		if remd[i] + remd[j] >= k:
			quotient += (remd[i] + remd[j]) // k
			i += 1
			j -= 1
		elif remd[i] + remd[j] < k:
			i += 1
	print(quotient)


t = int(input())
for i in range(t):
	first = input().split(' ')
	n = int(first[0])
	k = int(first[1])
	x = list(map(int, input().split(' ')))
	total = 0
	for j in range(n):
		total += int(x[j] / k)
		x[j] = x[j] % k
	x.sort()
	front = 0
	end = n - 1
	while front < end:
		if x[front] + x[end] < k:
			front += 1
		else:
			front += 1
			end -= 1
			total += 1
	print(total)


for _ in range(int(input())):
	(n, k) = map(int, input().split())
	arr = [int(i) for i in input().split()]
	ans = 0
	for i in range(len(arr)):
		ans += arr[i] // k
		arr[i] = arr[i] % k
	arr = sorted(arr, reverse=True)
	(i, j) = (0, n - 1)
	while i < j:
		if arr[i] + arr[j] < k:
			j -= 1
		else:
			(i, j) = (i + 1, j - 1)
			ans += 1
	print(ans)


for i in range(int(input())):
	(n, k) = map(int, input().split())
	A = [int(j) for j in input().split()]
	c = 0
	mod = []
	for j in range(n):
		c += A[j] // k
		mod.append(A[j] % k)
	mod.sort()
	s = 0
	e = n - 1
	while s < e:
		if mod[s] + mod[e] >= k:
			c += 1
			s += 1
			e -= 1
		else:
			s += 1
	print(c)


for T in range(int(input())):
	(n, k) = map(int, input().split())
	a = [int(val) for val in input().split()]
	res = 0
	for i in range(n):
		res += a[i] // k
		a[i] %= k
	a.sort()
	(l, r) = (0, n - 1)
	while l < r:
		if a[l] + a[r] >= k:
			res += 1
			r -= 1
		l += 1
	print(res)


t = int(input())
for i in range(t):
	(n, k) = map(int, input().split())
	l = list(map(int, input().split()))
	total = 0
	rem = []
	for j in range(n):
		total += l[j] // k
		rem.append(l[j] % k)
	rem.sort()
	low = 0
	high = n - 1
	while low < high:
		val = rem[low] + rem[high]
		if val >= k:
			total += val // k
			low += 1
			high -= 1
		else:
			low += 1
	print(total)


t = int(input())
for o in range(t):
	(n, k) = map(int, input().split())
	a = list(map(int, input().split()))
	ans = 0
	for i in range(n):
		ans += a[i] // k
		a[i] %= k
	a.sort()
	(l, r) = (0, n - 1)
	while l < r:
		while l <= r and a[l] + a[r] < k:
			l += 1
		if l >= r:
			break
		ans += (a[l] + a[r]) // k
		(l, r) = (l + 1, r - 1)
	print(ans)


for _ in range(int(input())):
	(n, k) = list(map(int, input().split()))
	l = list(map(int, input().split()))
	ans = 0
	for i in range(n):
		ans += l[i] // k
		l[i] = l[i] % k
	l.sort()
	vel = 0
	i = 0
	while i < n:
		if i != n - 1 and l[i] + l[-1] >= k:
			ans += 1
			l.pop()
			n -= 1
		else:
			vel += 1
		i += 1
	print(ans)


iT = int(input())
for _ in range(iT):
	(iN, iK) = map(int, input().split())
	lst_temp = list(map(int, input().split()))
	lst_temp.sort(reverse=True)
	temp = [0] * iN
	ans = 0
	for i in range(iN):
		ans += lst_temp[i] // iK
		temp[i] = lst_temp[i] % iK
	temp.sort(reverse=True)
	i = 0
	j = iN - 1
	while i < j:
		if temp[i] + temp[j] >= iK:
			i += 1
			j -= 1
			ans += 1
		else:
			j -= 1
	print(ans)


for _ in range(int(input())):
	(n, k) = map(int, input().split())
	arr = list(map(int, input().split(' ')))
	s = sum(arr)
	seen = set()
	N = len(arr)
	cost = 0
	for i in range(N):
		arr[i] = arr[i] % k
	arr.sort()
	(left, right) = (0, N - 1)
	rem = 0
	while left < N and right > left:
		if arr[left] + arr[right] == k:
			left += 1
			right -= 1
		elif arr[left] + arr[right] < k:
			rem += arr[left]
			left += 1
		elif arr[left] + arr[right] > k:
			rem += (arr[left] + arr[right]) % k
			left += 1
			right -= 1
	print((s - rem) // k)


tests = int(input())
for _ in range(tests):
	x = list(map(int, input().split()))
	n = int(x[0])
	k = int(x[1])
	a = list(map(int, input().split()))
	total = sum(a)
	if k == 1:
		print(total)
	else:
		remainder = 0
		a.sort(key=lambda i: i % k)
		l = 0
		r = n - 1
		while r >= l:
			if a[r] % k + a[l] % k < k:
				if a[l] % k != 0:
					remainder += a[l] % k
			else:
				if a[r] % k + a[l] % k > k:
					remainder += (a[l] % k + a[r] % k) % k
				r -= 1
			l += 1
		print((total - remainder) // k)


import math
for _ in range(int(input())):
	(n, k) = map(int, input().split())
	arr = list(map(int, input().split()))
	sum = 0
	for i in range(n):
		sum += math.floor(arr[i] / k)
	arr1 = []
	for i in range(n):
		arr1.append(arr[i] % k)
	arr1.sort()
	low = 0
	high = n - 1
	while low < high:
		if arr1[low] + arr1[high] >= k:
			sum += 1
			low += 1
			high -= 1
		elif arr1[low] + arr1[high] < k:
			low += 1
	print(sum)


t = int(input())
for q in range(t):
	two = input().split()
	n = int(two[0])
	k = int(two[1])
	wi = input().split()
	r = []
	zh = 0
	for i in range(n):
		r.append(int(wi[i]) % k)
		zh += int(wi[i]) // k
	r.sort(reverse=True)
	head = 0
	tail = n - 1
	while head < tail:
		if r[head] + r[tail] >= k:
			zh += 1
			head += 1
			tail -= 1
		else:
			tail -= 1
	print(zh)


import math
t = int(input())
while t > 0:
	(n, k) = [int(i) for i in input().split()]
	sum = 0
	a = []
	for i in input().split():
		sum += math.floor(int(i) / k)
		a.append(int(i) % k)
	a.sort()
	i = 0
	j = n - 1
	while i < j:
		if a[i] + a[j] >= k:
			sum += 1
			i += 1
			j -= 1
		else:
			i += 1
	print(sum)
	t -= 1


import math
for h in range(int(input())):
	(n, k) = map(int, input().split())
	x = list(map(int, input().split()))
	z = []
	for i in range(n):
		if x[i] % k != 0:
			z.append(x[i] % k)
		x[i] = x[i] // k
	z.sort()
	(i, j) = (0, len(z) - 1)
	c = 0
	while j >= 0:
		while i < j and z[i] + z[j] < k:
			i += 1
		if i < j and z[i] + z[j] >= k:
			c += 1
		j -= 1
		i += 1
	print(c + sum(x))


from math import floor

def new_sort(s, return_index=False):
	if return_index:
		return (sorted(s), sorted(range(len(s)), key=lambda k: s[k]))
	else:
		return sorted(s)
t = int(input())
for _ in range(t):
	(n, k) = [int(x) for x in str(input()).split()]
	a = [int(x) for x in str(input()).split()]
	modules = [x % k for x in a]
	(sorted_modules, index) = new_sort(modules, return_index=True)
	p1 = 0
	p2 = n - 1
	num_iters = n // 2
	profit = 0
	for _ in range(num_iters):
		if sorted_modules[p1] + sorted_modules[p2] >= k:
			profit += floor((a[index[p1]] + a[index[p2]]) / k)
			p1 += 1
			p2 -= 1
		else:
			profit += floor((a[index[p1]] + a[index[p1 + 1]]) / k)
			p1 += 2
	print(profit)


for time in range(int(input())):
	(n, k) = map(int, input().split())
	nums = [int(a) for a in input().split()]
	rem = {}
	s = 0
	for j in nums:
		s += j
		l = j % k
		if l == 0:
			if 0 in rem:
				del rem[0]
			else:
				rem[0] = 1
		elif k - l in rem:
			rem[k - l] -= 1
			if rem[k - l] == 0:
				del rem[k - l]
		elif l in rem:
			rem[l] += 1
		else:
			rem[l] = 1
	d = sum((j * rem[j] for j in rem))
	s -= d
	d = s // k
	sorte = sorted(list(rem))
	maxi = len(sorte) - 1
	mini = 0
	while maxi >= mini:
		maindex = sorte[maxi]
		miindex = sorte[mini]
		if maindex + miindex < k:
			mini += 1
			continue
		if maxi == mini:
			d += rem[maindex] // 2
			break
		dif = min(rem[maindex], rem[miindex])
		d += dif
		rem[maindex] -= dif
		rem[miindex] -= dif
		if rem[maindex] == 0:
			maxi -= 1
		if rem[miindex] == 0:
			mini += 1
	print(d)


from operator import is_, truediv
from posixpath import split
t = int(input())
for _ in range(t):
	(n, k) = list(map(int, input().split()))
	arr = list(map(int, input().split()))
	temp = [[i, i % k, 0] for i in arr]
	temp = sorted(temp, key=lambda x: x[1])
	start = 0
	end = len(temp) - 1
	ans = 0
	while start < end:
		if temp[start][1] + temp[end][1] >= k:
			ans += int((temp[start][0] + temp[end][0]) / k)
			temp[start][2] = 1
			temp[end][2] = 1
			start += 1
			end -= 1
		else:
			start += 1
	is_first = True
	t = 0
	for i in range(len(temp) - 1, -1, -1):
		if temp[i][2] == 0:
			if is_first:
				t += temp[i][0]
				is_first = False
			else:
				t += temp[i][0]
				ans += int(t / k)
				is_first = True
				t = 0
	print(ans)


t = int(input())
for testtest in range(t):
	(n, k) = map(int, input().split())
	A = list(map(int, input().split()))
	ans = 0
	for i in range(n):
		ans += A[i] // k
		A[i] = A[i] % k
	A.sort()
	X = [0] * n
	a = 0
	b = n - 1
	while a < b and a < len(A) and (b > 0) and (A[a] <= k // 2):
		if A[a] + A[b] > k:
			b -= 1
			continue
		elif A[a] + A[b] < k:
			a += 1
			continue
		else:
			(X[a], X[b]) = (1, 1)
			a += 1
			b -= 1
			ans += 1
			continue
	AA = []
	for i in range(n):
		if X[i] == 0:
			AA += [A[i]]
	a = 0
	b = len(AA) - 1
	while a < b and a < len(AA) and (b > -1):
		if AA[a] + AA[b] < k:
			a += 1
			continue
		else:
			a += 1
			b -= 1
			ans += 1
			continue
	print(ans)


for _ in range(int(input())):
	(n, k) = map(int, input().split(' '))
	a = list(map(int, input().split(' ')))
	m = {}
	r = []
	ans = 0
	for ai in a:
		ans += ai // k
		mr = ai % k
		if mr not in m.keys():
			m[mr] = 1
		else:
			m[mr] += 1
	ml = list(m.keys())
	ml.sort()
	x = 0
	while x < len(ml):
		i = ml[x]
		if i > k // 2:
			break
		if k - i == i:
			ans += m[i] // 2
			if m[i] % 2 == 1:
				r.append(i)
		else:
			j = m.get(k - i, 0)
			d = min(m[i], j)
			ans += d
			m[i] -= d
			for _ in range(m[i]):
				r.append(i)
			if j != 0:
				m[k - i] -= d
		x += 1
	while x < len(ml):
		i = ml[x]
		for _ in range(m[i]):
			r.append(i)
		x += 1
	r.sort()
	(x, y) = (0, len(r) - 1)
	while x < y:
		if r[x] + r[y] >= k:
			ans += 1
			x += 1
			y -= 1
		else:
			x += 1
	print(ans)


def CF797E(numbers, k):
	answer = 0
	nums = []
	for num in numbers:
		answer += num // k
		nums.append(num % k)
	counts = {}
	for num in nums:
		counts[num] = counts.get(num, 0) + 1
	if k == 2:
		return answer if 1 not in counts else answer + counts[1] // 2
	temp = max(counts.keys())
	start = k - temp
	for i in range(temp, 1, -1):
		if i not in counts:
			continue
		start = max(start, k - i)
		while counts[i]:
			for j in range(start, k):
				if j not in counts or not counts[j]:
					continue
				if i == j and counts[i] == 1:
					continue
				start = j
				counts[j] -= 1
				counts[i] -= 1
				answer += 1
				break
			else:
				break
		else:
			continue
		break
	return answer
for _ in range(int(input())):
	(_, k) = map(int, input().split())
	print(CF797E(list(map(int, input().split())), k))