We define the following:

A subarray of array $a$ of length $n$ is a contiguous segment from $a[i]$ through $a[j]$ where $0\leq i\leq j<n.$.
The sum of an array is the sum of its elements.

Given an $n$ element array of integers, $a$, and an integer, $m$, determine the maximum value of the sum of any of its subarrays modulo $m$. 

Example 

$a=[1,2,3]$ 

$m=2$     

The following table lists all subarrays and their moduli:

		sum	%2
[1]		1	1
[2]		2	0
[3]		3	1
[1,2]		3	1
[2,3]		5	1
[1,2,3]		6	0

The maximum modulus is $unrecognized$.

Function Description

Complete the maximumSum function in the editor below.  

maximumSum has the following parameter(s):

long a[n]: the array to analyze   
long m: the modulo divisor   

Returns 

- long: the maximum (subarray sum modulo $m$)   

Input Format

The first line contains an integer $q$, the number of queries to perform.

The next $q$ pairs of lines are as follows:

The first line contains two space-separated integers $n$ and (long)$m$, the length of $a$ and the modulo divisor.  
The second line contains $n$ space-separated long integers $a[i]$.

Constraints

$2\leq n\leq10^{5}$  
$1\leq m\leq10^{14}$  
$1\leq a[i]\leq10^{18}$  
$2\leq\$ the sum of $n$ over all test cases $\leq\mathop{\mathrm{5}}\times10^{5}$   

Sample Input
STDIN       Function
-----       --------
1           q = 1
5 7         a[] size n = 5, m = 7
3 3 9 9 5

Sample Output
6

Explanation

The subarrays of array $a=[3,3,9,9,5]$ and their respective sums modulo $m=7$ are ranked in order of length and sum in the following list:


$1 .[9]\Rightarrow9\%7=2\mathrm{and}[9]\rightarrow9\%7=2 $
$[3]\Rightarrow3\%7=3\mathrm{and}[3]\rightarrow3\%7=3 $
$[5]\Rightarrow5\%7=5 $

$2. [9,5]\Rightarrow14\%7=0  $
$[9,9]\Rightarrow18\%7=4 $
$[3,9]\Rightarrow12\%7=5 $
$[3,3]\Rightarrow6\%7=6 $

$3. [3,9,9]\Rightarrow21\%7=0 $
$[3,3,9]\Rightarrow15\%7=1 $
$[9,9,5]\Rightarrow23\%7=2 $

$ 4.[3,3,9,9]\Rightarrow24\%7=3  $
$[3,9,9,5]\Rightarrow26\%7=5 $

$5[3,3,9,9,5]\Rightarrow29\%7=1$

The maximum value for $subarray sum \%7$ for any subarray is $6$.

Source: hackerrank | Difficulty: MEDIUM_HARD
Tags: Complete search


Solutions:
import bisect
t = int(input())
for _ in range(t):
	(n, m) = map(int, input().split())
	a = list(map(int, input().split()))
	csum = [a[0] % m]
	for x in a[1:]:
		csum.append((csum[-1] + x) % m)
	seen = [0]
	mx = -1
	for s in csum:
		idx = bisect.bisect_left(seen, s)
		if idx < len(seen):
			mx = max(mx, s, (s - seen[idx]) % m)
		else:
			mx = max(mx, s)
		bisect.insort_left(seen, s)
	print(mx)


from bisect import bisect, insort
T = int(input())
for _ in range(T):
	(N, M) = [int(i) for i in input().split()]
	ar = [int(i) for i in input().split()]
	cumulative_sums = []
	sum_so_far = 0
	max_sum = 0
	for i in range(N):
		sum_so_far = (sum_so_far + ar[i]) % M
		pos = bisect(cumulative_sums, sum_so_far)
		d = 0 if pos == i else cumulative_sums[pos]
		max_sum = max(max_sum, (sum_so_far + M - d) % M)
		insort(cumulative_sums, sum_so_far)
	print(max_sum)


from fileinput import input
import sys

def find():
	lines = input()
	noc = [int(x) for x in lines[0].strip().split()][0]
	for i in range(1, 1 + noc):
		(n, m) = [int(x) for x in lines[2 * (i - 1) + 1].strip().split()]
		a = [int(x) for x in lines[2 * (i - 1) + 2].strip().split()]
		sum = []
		total = 0
		for i in range(n):
			total = (total + a[i] % m) % m
			sum.append((total, i))
		sum.sort(key=lambda x: x[0])
		mod = m
		for i in range(1, n):
			(pre, idx1) = sum[i - 1]
			(cur, idx2) = sum[i]
			diff = cur - pre
			if idx1 > idx2 and diff > 0 and (diff < mod):
				mod = diff
				if diff == 1:
					break
		res = (m - mod) % m
		res = max(res, sum[-1][0])
		print(res, end='\n')
find()


import math
import sys
import string
import itertools
from bisect import bisect
from collections import *

def binary_search(a, x, lo=0, hi=-1):
	i = bisect(a, x, lo, hi)
	if i == 0:
		return 0
	elif a[i - 1] == x:
		return binary_search(a[:i - 1], x)
	else:
		return i
t = int(input())
while t:
	(n, m) = [int(x) for x in input().split()]
	arr = [int(x) for x in input().split()]
	s = []
	mx = 0
	p = 0
	for i in range(n):
		p = (p + arr[i]) % m
		mx = max(mx, p)
		j = binary_search(s, p + 1)
		if j != i:
			mx = max(mx, m + p - s[j])
		s.insert(j, p)
	print(mx)
	t -= 1


for _ in range(int(input())):
	(N, M) = map(int, input().split())
	A = [int(a) for a in input().split()]
	b = 0
	B = [b]
	for a in A:
		b = (a + b) % M
		B.append(b)
	order = sorted(range(len(B)), key=lambda i: B[i])
	best = 0
	lenB = len(B)
	for (a, j) in enumerate(order):
		if j == 0:
			continue
		a = (a + 1) % lenB
		i = order[a]
		Bj = B[j]
		ii = 0
		while i >= j or B[i] == Bj:
			a = (a + 1) % lenB
			i = order[a]
			ii += 1
			if ii > 100:
				break
		this = (Bj - B[i]) % M
		if this > best:
			best = this
	print(best)


import bisect
t = int(input())
for _ in range(t):
	(n, m) = map(int, input().split())
	a = list(map(int, input().split()))
	csum = [a[0] % m]
	for x in a[1:]:
		csum.append((csum[-1] + x) % m)
	seen = [0]
	mx = -1
	for s in csum:
		idx = bisect.bisect_left(seen, s)
		if idx < len(seen):
			mx = max(mx, s, (s - seen[idx]) % m)
		else:
			mx = max(mx, s)
		bisect.insort_left(seen, s)
	print(mx)


import bisect
for t in range(int(input())):
	(n, m) = [int(x) for x in input().split()]
	A = [int(x) for x in input().split()]
	prefixsum = [A[0] % m]
	for i in range(1, len(A)):
		prefixsum += [(A[i] + prefixsum[i - 1]) % m]
	toTheLeft = [0]
	mx = -1
	for pfs in prefixsum:
		pi = bisect.bisect_left(toTheLeft, pfs)
		if pi < len(toTheLeft):
			mx = max(mx, pfs, (pfs - toTheLeft[pi]) % m)
		else:
			mx = max(mx, pfs)
		bisect.insort_left(toTheLeft, pfs)
	print(mx)


from bisect import bisect_right
T = int(input())
for _ in range(T):
	(N, M) = [int(x) for x in input().split()]
	s = 0
	maxm = 0
	acc = [0]
	for (i, x) in enumerate(map(int, input().split())):
		s += x
		s %= M
		idx = bisect_right(acc, s)
		if idx > i:
			maxm = max(maxm, s)
		else:
			maxm = max(maxm, M + s - acc[idx])
		acc.insert(idx, s)
	print(maxm)


import sys
import bisect
RED = 31
GREEN = 32
ESCAPE = '%s[' % chr(27)
RESET = '%s0m' % ESCAPE
FORMAT = '1;%dm'

def colorize(text, color):
	return ESCAPE + FORMAT % (color,) + text + RESET

def prefix_sum(xs, modulo):
	cumsum = 0
	result = list()
	for x in xs:
		cumsum = (cumsum + x) % modulo
		result.append(cumsum)
	return result

def solve(xs, M):
	xs = [0] + xs
	cumsum = xs[0]
	cumsums = [cumsum]
	maximum = -sys.maxsize
	for (j, x) in enumerate(xs[1:]):
		cumsum = (cumsum + x) % M
		candidate_index = bisect.bisect(cumsums, (cumsum - M) % M)
		if candidate_index < len(cumsums):
			maximum = max(maximum, (cumsum - cumsums[candidate_index]) % M)
		else:
			maximum = max(maximum, cumsum)
		bisect.insort(cumsums, cumsum)
	return maximum
T = int(sys.stdin.readline())
for case in range(T):
	[N_, M] = [int(X) for X in sys.stdin.readline().split()]
	xs = [int(X) for X in sys.stdin.readline().split()]
	print(solve(xs, M))


def smallest_bigger_int(A, x):
	low = 0
	high = len(A) - 1
	while low < high:
		mid = int((low + high) / 2)
		if A[mid] <= x:
			low = mid + 1
		elif A[mid] > x:
			high = mid
	return A[low]

def max_diff(B, N, M):
	if N == 1:
		return B[0]
	elif N <= 0:
		return 0
	halfN = int(N / 2)
	out1 = max_diff(B[:halfN], halfN, M)
	out2 = max_diff(B[halfN:], N - halfN, M)
	B1 = sorted(B[:halfN])
	B2 = sorted(B[halfN:])
	out3 = 0
	ind1 = 0
	is_overflow = 0
	for ind2 in range(len(B2)):
		while is_overflow == 0 and ind1 < halfN and (B1[ind1] <= B2[ind2]):
			ind1 += 1
		if ind1 == halfN:
			ind1 = 0
			is_overflow = 1
		if out3 < (B2[ind2] - B1[ind1]) % M:
			out3 = (B2[ind2] - B1[ind1]) % M
	out = max(out1, out2, out3)
	return out
T = int(input())
for t in range(T):
	(N, M) = input().split()
	N = int(N)
	M = int(M)
	A = input().split()
	B = [0 for i in range(len(A))]
	A[0] = int(A[0]) % M
	B[0] = A[0]
	for i in range(1, N):
		A[i] = int(A[i])
		B[i] = (B[i - 1] + A[i]) % M
	out = max_diff(B, N, M)
	print(out)


import bisect

def maxSum(A, K):
	cumu = []
	maxi = 0
	pre = 0
	for a in A:
		v = (a + pre) % K
		i = bisect.bisect_right(cumu, v)
		if i == len(cumu):
			maxi = max(v, maxi)
		else:
			maxi = max((v - cumu[i]) % K, maxi)
		cumu.insert(i, v)
		pre = v
	return maxi
for _ in range(int(input())):
	(N, K) = [int(i) for i in input().split()]
	A = [int(i) % K for i in input().split()]
	print(maxSum(A, K))


import bisect
t = int(input())
for _ in range(t):
	(n, m) = map(int, input().split())
	a = list(map(int, input().split()))
	csum = [a[0] % m]
	for x in a[1:]:
		csum.append((csum[-1] + x) % m)
	seen = [0]
	mx = -1
	for s in csum:
		idx = bisect.bisect_left(seen, s)
		if idx < len(seen):
			mx = max(mx, s, (s - seen[idx]) % m)
		else:
			mx = max(mx, s)
		bisect.insort_left(seen, s)
	print(mx)


import fileinput
inputs = []
for line in fileinput.input():
	inputs.append([int(i) for i in line.strip().split()])
T = inputs[0][0]

class Node:

	def __init__(self, key):
		self.key = key
		self.parent = None
		self.leftChild = None
		self.rightChild = None
		self.height = 0

	def max_children_height(self):
		if self.leftChild and self.rightChild:
			return max(self.leftChild.height, self.rightChild.height)
		elif self.leftChild and (not self.rightChild):
			return self.leftChild.height
		elif not self.leftChild and self.rightChild:
			return self.rightChild.height
		else:
			return -1

	def balance(self):
		return (self.leftChild.height if self.leftChild else -1) - (self.rightChild.height if self.rightChild else -1)

class AVLTree:

	def __init__(self):
		self.rootNode = None
		self.elements_count = 0
		self.rebalance_count = 0

	def height(self):
		if self.rootNode:
			return self.rootNode.height
		else:
			return 0

	def rebalance(self, node_to_rebalance):
		self.rebalance_count += 1
		A = node_to_rebalance
		F = A.parent
		if node_to_rebalance.balance() == -2:
			if node_to_rebalance.rightChild.balance() <= 0:
				B = A.rightChild
				C = B.rightChild
				A.rightChild = B.leftChild
				if A.rightChild:
					A.rightChild.parent = A
				B.leftChild = A
				A.parent = B
				if F is None:
					self.rootNode = B
					self.rootNode.parent = None
				else:
					if F.rightChild == A:
						F.rightChild = B
					else:
						F.leftChild = B
					B.parent = F
				self.recompute_heights(A)
				self.recompute_heights(B.parent)
			else:
				B = A.rightChild
				C = B.leftChild
				B.leftChild = C.rightChild
				if B.leftChild:
					B.leftChild.parent = B
				A.rightChild = C.leftChild
				if A.rightChild:
					A.rightChild.parent = A
				C.rightChild = B
				B.parent = C
				C.leftChild = A
				A.parent = C
				if F is None:
					self.rootNode = C
					self.rootNode.parent = None
				else:
					if F.rightChild == A:
						F.rightChild = C
					else:
						F.leftChild = C
					C.parent = F
				self.recompute_heights(A)
				self.recompute_heights(B)
		elif node_to_rebalance.leftChild.balance() >= 0:
			B = A.leftChild
			C = B.leftChild
			A.leftChild = B.rightChild
			if A.leftChild:
				A.leftChild.parent = A
			B.rightChild = A
			A.parent = B
			if F is None:
				self.rootNode = B
				self.rootNode.parent = None
			else:
				if F.rightChild == A:
					F.rightChild = B
				else:
					F.leftChild = B
				B.parent = F
			self.recompute_heights(A)
			self.recompute_heights(B.parent)
		else:
			B = A.leftChild
			C = B.rightChild
			A.leftChild = C.rightChild
			if A.leftChild:
				A.leftChild.parent = A
			B.rightChild = C.leftChild
			if B.rightChild:
				B.rightChild.parent = B
			C.leftChild = B
			B.parent = C
			C.rightChild = A
			A.parent = C
			if F is None:
				self.rootNode = C
				self.rootNode.parent = None
			else:
				if F.rightChild == A:
					F.rightChild = C
				else:
					F.leftChild = C
				C.parent = F
			self.recompute_heights(A)
			self.recompute_heights(B)

	def recompute_heights(self, start_from_node):
		changed = True
		node = start_from_node
		while node and changed:
			old_height = node.height
			node.height = node.max_children_height() + 1 if node.rightChild or node.leftChild else 0
			changed = node.height != old_height
			node = node.parent

	def insert(self, key, res):
		node = Node(key)
		if not self.rootNode:
			self.rootNode = node
		else:
			res = self.add_as_child(self.rootNode, node, res)
		return res

	def add_as_child(self, parent, child, res):
		node_to_rebalance = None
		while child.key != parent.key:
			if child.key < parent.key:
				val = M + child.key - parent.key
				if val > res:
					res = val
				if not parent.leftChild:
					parent.leftChild = child
					child.parent = parent
					self.elements_count += 1
					if parent.height == 0 and self.height() < 14:
						node = parent
						while node:
							node.height = node.max_children_height() + 1
							if not node.balance() in [-1, 0, 1]:
								node_to_rebalance = node
								break
							node = node.parent
					break
				else:
					parent = parent.leftChild
			elif not parent.rightChild:
				parent.rightChild = child
				child.parent = parent
				self.elements_count += 1
				if parent.height == 0 and self.height() < 14:
					node = parent
					while node:
						node.height = node.max_children_height() + 1
						if not node.balance() in [-1, 0, 1]:
							node_to_rebalance = node
							break
						node = node.parent
				break
			else:
				parent = parent.rightChild
		if node_to_rebalance:
			self.rebalance(node_to_rebalance)
		return res
for t in range(1, T + 1):
	(N, M, A) = (inputs[t * 2 - 1][0], inputs[t * 2 - 1][1], inputs[t * 2])
	(res, s) = (0, [])
	for i in A:
		res = (res + i) % M
		s.append(res)
	res = max(s)
	tree = AVLTree()
	for j in s:
		res = tree.insert(j, res)
	print(res)


from bisect import bisect, insort
tests = int(input())
for _ in range(tests):
	(n, m) = map(int, input().split())
	l = list(map(int, input().split()))
	pre = []
	s = 0
	maxx = 0
	for e in l:
		s = (e % m + s) % m
		pre.append(s)
		if s > maxx:
			maxx = s
	tree = [pre[0]]
	for i in range(1, n):
		current = pre[i]
		closest = bisect(tree, current)
		if closest < len(tree):
			current_sum = (current - tree[closest]) % m
			if current_sum > maxx:
				maxx = current_sum
		insort(tree, pre[i])
	print(maxx)


T = int(input())
for _ in range(T):
	NM = [int(x) for x in input().split()]
	(N, M) = (NM[0], NM[1])
	A = [int(x) for x in input().split()]
	prefixSums = [(0, 0)] * len(A)
	for i in range(len(A)):
		prefixSums[i] = ((prefixSums[i - 1][0] + A[i]) % M, i)
	prefixSums.append((0, -1))
	prefixSums.append((M, -1))
	prefixSums = sorted(prefixSums)
	(maxDiff, idx1, idx2) = (0, 0, 0)
	for i in range(1, len(prefixSums)):
		(prevMod, prevIdx) = prefixSums[i - 1]
		(currMod, currIdx) = prefixSums[i]
		if currIdx > prevIdx and (currMod - prevMod) % M > maxDiff:
			(maxDiff, idx1, idx2) = ((currMod - prevMod) % M, prevIdx, currIdx)
		if currIdx < prevIdx and (prevMod - currMod) % M > maxDiff:
			(maxDiff, idx1, idx2) = ((prevMod - currMod) % M, currIdx, prevIdx)
	print(maxDiff)


class Node:

	def __init__(self, data):
		self.data = data
		self.leftChild = None
		self.rightChild = None
		self.parent = None
		self.red = False

class BinaryTree:

	def __init__(self):
		self.head = None
		self.count = 0

	def is_empty(self):
		return self.count == 0

	def reset(self):
		self.__init__()

	def insert_aux(self, node):
		ret = None
		z = node
		if self.is_empty():
			self.head = node
			self.count += 1
		else:
			self.count += 1
			node.red = True
			ret = self.insert(node, self.head, ret)
		if ret is not None:
			return z.data - ret.data
		else:
			return z.data

	def insert(self, node, position, ret):
		if node.data < position.data:
			ret = position
			if position.leftChild == None:
				position.leftChild = node
				node.parent = position
				tmp = ret
				self.insertFixUp(node)
				node.red = True
				return tmp
			else:
				return self.insert(node, position.leftChild, ret)
		elif position.rightChild == None:
			position.rightChild = node
			node.parent = position
			tmp = ret
			self.insertFixUp(node)
			node.red = True
			return tmp
		else:
			return self.insert(node, position.rightChild, ret)

	def insertFixUp(self, node):
		while node.parent is not None and node.parent.red:
			if node.parent.parent.leftChild is not None and node.parent.data == node.parent.parent.leftChild.data:
				sibling = node.parent.parent.rightChild
				if sibling is not None and sibling.red:
					node.parent.red = False
					sibling.red = False
					node.parent.parent.red = True
					node = node.parent.parent
				else:
					if node.parent.rightChild is not None and node.data == node.parent.rightChild.data:
						node = node.parent
						self.leftRotate(node)
					node.parent.red = False
					node.parent.parent.red = True
					self.rightRotate(node.parent.parent)
			else:
				sibling = node.parent.parent.leftChild
				if sibling is not None and sibling.red:
					node.parent.red = False
					sibling.red = False
					node.parent.parent.red = True
					node = node.parent.parent
				else:
					if node.parent.leftChild is not None and node.data == node.parent.leftChild.data:
						node = node.parent
						self.rightRotate(node)
					node.parent.red = False
					node.parent.parent.red = True
					self.leftRotate(node.parent.parent)
		self.head.red = False

	def leftRotate(self, node):
		y = node.rightChild
		node.rightChild = y.leftChild
		if y.leftChild is not None:
			y.leftChild.parent = node
		y.parent = node.parent
		if node.parent is None:
			self.head = y
		elif node.data == node.parent.leftChild.data:
			node.parent.leftChild = y
		else:
			node.parent.rightChild = y
		y.leftChild = node
		node.parent = y

	def rightRotate(self, node):
		y = node.leftChild
		node.leftChild = y.rightChild
		if y.rightChild is not None:
			y.rightChild.parent = node
		y.parent = node.parent
		if node.parent is None:
			self.head = y
		elif node.data == node.parent.rightChild.data:
			node.parent.rightChild = y
		else:
			node.parent.leftChild = y
		y.rightChild = node
		node.parent = y

def insert_array(Array):
	for item in Array:
		bTree.insert_aux(Node(item))
T = int(input())
for i in range(T):
	(N, M) = str(input()).split()
	array = str(input()).split()
	sum = 0
	bTree = BinaryTree()
	prefix = [None] * len(array)
	for i in range(len(array)):
		sum = (sum + int(array[i]) % int(M)) % int(M)
		prefix[i] = sum
	ret = 0
	for i in range(len(prefix)):
		newRet = bTree.insert_aux(Node(prefix[i]))
		if newRet < 0:
			newRet += int(M)
		ret = max(newRet, ret)
	print(ret)


import bisect

def scanl(f, base, l):
	for x in l:
		base = f(base, x)
		yield base

def solve(m, es):
	ms = tuple(scanl(lambda a, b: (a + b) % m, 0, es))
	pre_sum = []
	max_value = 0
	for n in ms:
		max_value = max(max_value, n)
		pos = bisect.bisect_right(pre_sum, n)
		if pos < len(pre_sum):
			max_value = max(max_value, n - pre_sum[pos] + m)
		bisect.insort_right(pre_sum, n)
	return max_value

def main():
	T = int(input())
	for _ in range(T):
		(N, M) = tuple((int(v) for v in input().split()))
		ES = tuple((int(v) for v in input().split()))
		print(solve(M, ES))
main()


import itertools
from random import random
import unittest
from fileinput import FileInput
import unittest

class SkipList(object):

	def __init__(self):
		self.tail = [2 ** 63 - 1]
		self.head = [-2 ** 31, self.tail]

	def find_lower(self, search_data, update):
		height = len(self.head)
		node = self.head
		for level in range(height - 1, 0, -1):
			next_node = node[level]
			while next_node[0] < search_data:
				node = next_node
				next_node = node[level]
			update[level - 1] = node
		return node

	def insert(self, data):
		height = len(self.head) - 1
		update = [None] * height
		node = self.find_lower(data, update)
		node_height = 1
		while random() < 0.5:
			node_height += 1
		for _ in range(node_height - height):
			self.head.append(self.tail)
			update.append(self.head)
		new_node = [data]
		for i in range(node_height):
			new_node.append(update[i][i + 1])
		for level in range(node_height):
			update[level][level + 1] = new_node

	def ceiling(self, search_data):
		height = len(self.head)
		node = self.head
		for level in range(height - 1, 0, -1):
			next_node = node[level]
			while next_node[0] < search_data:
				node = next_node
				next_node = node[level]
		candidate = node[1]
		if candidate is not self.tail:
			return candidate[0]
		else:
			return 0

def maximise(array, m):
	sums_seen = SkipList()
	sums_seen.insert(0)
	mod_running = 0
	best = 0
	for num in array:
		mod_running = (mod_running + num) % m
		sums_seen.insert(mod_running)
		goal = (mod_running + 1) % m
		nearest_goal = sums_seen.ceiling(goal)
		best = max(best, (mod_running - nearest_goal) % m)
	return best

class TestMaximise(unittest.TestCase):

	def test_single(self):
		a = [1]
		m = 2
		actual = maximise(a, m)
		expected = 1
		self.assertEqual(actual, expected)

	def test_single_overflow(self):
		a = [3]
		m = 2
		actual = maximise(a, m)
		expected = 1
		self.assertEqual(actual, expected)

	def test_example(self):
		self.assertEqual(maximise([3, 3, 9, 9, 5], 7), 6)

	def test_zeroes(self):
		self.assertEqual(maximise([0, 0, 0], 1), 0)
		self.assertEqual(maximise([0, 0, 0], 3), 0)

	def test_ones(self):
		self.assertEqual(maximise([1, 1, 1, 1], 1), 0)
		self.assertEqual(maximise([1, 1, 1, 1], 2), 1)
		self.assertEqual(maximise([1, 1, 1, 1], 3), 2)
		self.assertEqual(maximise([1, 1, 1, 1], 4), 3)

	def test_simple(self):
		self.assertEqual(maximise([5, 4], 7), 5)
		self.assertEqual(maximise([3, 1, 2], 7), 6)
		self.assertEqual(maximise([1, 1, 8], 7), 3)

def main():
	with FileInput('-') as file:
		num_cases = int(file.readline())
		for _ in range(num_cases):
			(size, mod) = [int(x) for x in file.readline().split()]
			array = [int(x) for x in file.readline().split()]
			print(maximise(array, mod))
main()


from operator import itemgetter
T = int(input())
for _ in range(T):
	(N, M) = map(int, input().split())
	array = list(map(int, input().split()))
	helper = []
	sum_ = 0
	max_sum = 0
	for (i, element) in enumerate(array):
		sum_ = (sum_ + element) % M
		helper.append((i, sum_))
		max_sum = max(sum_, max_sum)
	helper.sort(key=itemgetter(1))
	(i, sum_) = helper[0]
	for (ni, nsum_) in helper[1:]:
		if ni < i:
			max_sum = max(M - nsum_ + sum_, max_sum)
		(i, sum_) = (ni, nsum_)
	print(max_sum)


import bisect

def max_sum_modulo(values, n, m):
	presum = []
	total = 0
	for i in range(0, n):
		total += values[i]
		total = total % m
		presum.append(total)
	top = max(presum)
	hits = {}
	for i in range(0, n):
		v = presum[i]
		hits[v] = min(hits.get(v, i + 1), i)
	sorted_keys = sorted(hits.keys())
	for i in range(1, n):
		max_diff = m - top
		left = bisect.bisect_right(sorted_keys, presum[i])
		right = bisect.bisect_left(sorted_keys, presum[i] + max_diff) - 1
		if right >= left:
			for j in range(left, right + 1):
				v = sorted_keys[j]
				if hits[v] < i:
					r = (presum[i] - v) % m
					top = max(top, r)
	return top
t = int(input())
for i in range(0, t):
	(n, m) = [int(v) for v in input().split()]
	values = [int(v) for v in input().split()]
	print(max_sum_modulo(values, n, m))


class RBTNode(object):

	def __init__(self, key):
		self.key = key
		self.parent = None
		self.left = None
		self.right = None
		self.colorBlack = True

class RedBlackTree(object):

	def __init__(self, root):
		self.root = root
		self.nilNode = RBTNode(-1)

	def leftRotation(self, node):
		y = node.right
		node.right = y.left
		if y.left is not self.nilNode:
			y.left.parent = node
		y.parent = node.parent
		if node.parent is self.nilNode:
			self.root = y
		elif node == node.parent.left:
			node.parent.left = y
		else:
			node.parent.right = y
		y.left = node
		node.parent = y

	def rightRotation(self, node):
		x = node.left
		node.left = x.right
		if x.right is not self.nilNode:
			x.right.parent = node
		x.parent = node.parent
		if node.parent is self.nilNode:
			self.root = x
		elif node == node.parent.left:
			node.parent.left = x
		else:
			node.parent.right = x
		x.right = node
		node.parent = x

	def insert(self, node):
		last = None
		current = self.root
		while current is not self.nilNode:
			last = current
			if current.key > node.key:
				current = current.left
			else:
				current = current.right
		node.parent = last
		if last is self.nilNode:
			self.root = node
		elif node.key < last.key:
			last.left = node
		else:
			last.right = node
		node.colorBlack = False
		node.left = self.nilNode
		node.right = self.nilNode
		self.insertFix(node)

	def insertFix(self, node):
		while not node.parent.colorBlack:
			if node.parent == node.parent.parent.left:
				y = node.parent.parent.right
				if not y.colorBlack:
					node.parent.colorBlack = True
					y.colorBlack = True
					node.parent.parent.colorBlack = False
					node = node.parent.parent
				else:
					if node == node.parent.right:
						node = node.parent
						self.leftRotation(node)
					node.parent.colorBlack = True
					node.parent.parent.colorBlack = False
					self.rightRotation(node.parent.parent)
			else:
				y = node.parent.parent.left
				if not y.colorBlack:
					node.parent.colorBlack = True
					y.colorBlack = True
					node.parent.parent.colorBlack = False
					node = node.parent.parent
				else:
					if node == node.parent.left:
						node = node.parent
						self.rightRotation(node)
					node.parent.colorBlack = True
					node.parent.parent.colorBlack = False
					self.leftRotation(node.parent.parent)
		self.root.colorBlack = True

	def searchMax(self, elem):
		current = self.root
		maxV = None
		while current is not self.nilNode:
			if current.key > elem and (maxV is None or maxV > current.key):
				maxV = current.key
			if current.key <= elem:
				current = current.right
			else:
				current = current.left
		return maxV

def maxSum(m, n, array):
	modSum = array[0] % m
	rbtRoot = RBTNode(modSum)
	rbTree = RedBlackTree(rbtRoot)
	rbtRoot.parent = rbTree.nilNode
	rbtRoot.left = rbTree.nilNode
	rbtRoot.right = rbTree.nilNode
	maxV = modSum
	for i in range(1, n):
		if maxV == m - 1:
			return maxV
		modSum = (modSum + array[i] % m) % m
		currentMax = rbTree.searchMax(modSum)
		if currentMax is None:
			currentMax = modSum
		else:
			currentMax = (modSum - currentMax + m) % m
		if currentMax > maxV:
			maxV = currentMax
		rbTree.insert(RBTNode(modSum))
	return maxV
t = int(input())
for i in range(t):
	(n, m) = input().split()
	(n, m) = (int(n), int(m))
	array = input().split()
	array = [int(i) for i in array]
	print(maxSum(m, n, array))


import bisect

def find_gt(a, x):
	i = bisect.bisect_right(a, x)
	if i != len(a):
		return a[i]
	raise ValueError

def search_sum(A, mod):
	P = []
	P.append(A[0] % mod)
	highest = P[0]
	tree = [P[-1]]
	for i in range(1, len(A)):
		p = A[i]
		P.append((P[-1] + p) % mod)
		if P[-1] == mod - 1:
			return mod - 1
		try:
			sec = find_gt(tree, P[-1])
		except ValueError:
			sec = 0
		result = (P[-1] - sec + mod) % mod
		highest = max(highest, result)
		bisect.insort(tree, P[-1])
	return highest
for _ in range(int(input())):
	(n, mod) = [int(x) for x in input().split()]
	A = [int(x) for x in input().split()]
	res = search_sum(A, mod)
	print(res)


T = int(input())
for T_i in range(T):
	(n, m) = [int(x) for x in input().split()]
	l = [int(x) % m for x in input().split()]
	sums = [l[0] % m]
	for i in range(1, n):
		sums.append((sums[i - 1] + l[i]) % m)
	result = max(sums)
	sumsx = {}
	for i in range(n):
		if not sumsx.__contains__(sums[i]):
			sumsx[sums[i]] = i
	sums = sorted([(i, sumsx[i]) for i in sumsx])
	for i in range(len(sums)):
		val = sums[i][0]
		for k in range(i + 1, len(sums)):
			check = sums[k][0]
			if (val - check + m) % m < result:
				break
			if sums[k][1] < sums[i][1]:
				result = (val - check + m) % m
	print(result)


from itertools import accumulate
from bisect import *
from random import *

class BSTNode(object):

	def __init__(self, value):
		self._left = None
		self._right = None
		self._parent = None
		self._value = value
		self._priority = random()

	def nextinorder(self):
		if self._right != None:
			return self._right.minvalue()
		cur = self._parent
		while cur != None and cur._value < self._value:
			cur = cur._parent
		if cur != None:
			return cur._value
		else:
			return None

	def minvalue(self):
		cur = self
		while cur._left != None:
			cur = cur._left
		return cur._value

class BinarySearchTree(object):

	def __init__(self):
		self._root = None

	def insert(self, value):
		cur = self._root
		if cur == None:
			self._root = BSTNode(value)
			return self._root
		while True:
			if value < cur._value:
				if cur._left is None:
					newnode = BSTNode(value)
					newnode._parent = cur
					cur._left = newnode
					self.rebalance(newnode)
					return newnode
				else:
					cur = cur._left
			elif value > cur._value:
				if cur._right is None:
					newnode = BSTNode(value)
					newnode._parent = cur
					cur._right = newnode
					self.rebalance(newnode)
					return newnode
				else:
					cur = cur._right
			else:
				return None

	def rebalance(self, node):
		while node._parent != None and node._parent._priority < node._priority:
			oldparent = node._parent
			newparent = oldparent._parent
			if newparent != None:
				if newparent._left == oldparent:
					newparent._left = node
				else:
					newparent._right = node
			if oldparent._right == node:
				oldchild = node._left
				node._left = oldparent
				oldparent._right = oldchild
			else:
				oldchild = node._right
				node._right = oldparent
				oldparent._left = oldchild
			if oldchild != None:
				oldchild._parent = oldparent
			oldparent._parent = node
			node._parent = newparent
			if newparent is None:
				self._root = node
t = int(input())
for _t in range(t):
	[n, m] = [int(s) for s in input().split()]
	arr = [int(s) % m for s in input().split()]
	arr_cumsum = [0]
	arr_cumsum.extend(accumulate(arr, func=lambda x, y: (x + y) % m))
	best = 0
	curr = 0
	tree = BinarySearchTree()
	for x in arr_cumsum:
		node = tree.insert(x)
		if node != None:
			y = node.nextinorder()
			if y != None:
				curr = (x - y) % m
			else:
				curr = x
			if curr > best:
				best = curr
	print(best)


def solve(A, M):
	P = [(0, -1)]
	for (i, a) in enumerate(A):
		P.append(((P[-1][0] + a) % M, i))
	P.sort()
	Pmin = [P[0]]
	for a in P:
		if a[0] == Pmin[-1][0]:
			continue
		else:
			Pmin.append(a)
	Pmax = [P[0]]
	for a in P:
		if a[0] == Pmax[-1][0]:
			Pmax[-1] = a
		else:
			Pmax.append(a)
	m = max(Pmax)[0]
	for (j, p) in enumerate(Pmax):
		for i in range(j + 1, len(Pmin)):
			if M - Pmin[i][0] + p[0] <= m:
				break
			if Pmin[i][1] < p[1]:
				m = M - Pmin[i][0] + p[0]
				break
	return m
for _ in range(int(input())):
	(N, M) = map(int, input().split())
	A = list(map(int, input().split()))
	print(solve(A, M))


for _ in range(int(input())):
	(n, m) = map(int, input().split())
	raw = map(int, input().split())
	prefix = [0]
	for num in raw:
		prefix.append((prefix[-1] + num % m) % m)
	res = max(prefix)
	increase = sorted(((prefix[i], i) for i in range(1, n + 1)))
	for i in range(n - 1):
		if increase[i][1] > increase[i + 1][1]:
			res = max(res, m - increase[i + 1][0] + increase[i][0])
	print(res)


from bisect import bisect_right

def solve(ar, m):
	p = [0]
	for x in ar:
		p.append((p[-1] + x) % M)
	d = m - max(p)
	pre = [0]
	for j in range(1, len(ar) + 1):
		if p[j] < pre[-1]:
			i = bisect_right(pre, p[j])
			d = min(d, pre[i] - p[j])
			pre.insert(i, p[j])
		else:
			pre.append(p[j])
	return m - d
for T in range(int(input())):
	(N, M) = [int(x) for x in input().split()]
	ar = [int(x) for x in input().split()]
	print(solve(ar, M))


class Node:

	def __init__(self, key):
		self.Key = key
		self.Parent = 0
		self.LeftChild = 0
		self.RightChild = 0
		self.BalanceFactor = 0

def SetLeftChild(parent, child):
	parent.LeftChild = child
	if child != 0:
		child.Parent = parent

def SetRightChild(parent, child):
	parent.RightChild = child
	if child != 0:
		child.Parent = parent

def RotateRight(node):
	global AVLRoot
	nodeParent = node.Parent
	newRoot = node.LeftChild
	nodeNewLeft = newRoot.RightChild
	if nodeParent != 0 and nodeParent.LeftChild == node:
		SetLeftChild(nodeParent, newRoot)
	elif nodeParent != 0 and nodeParent.RightChild == node:
		SetRightChild(nodeParent, newRoot)
	elif nodeParent == 0:
		newRoot.Parent = 0
		AVLRoot = newRoot
	SetRightChild(newRoot, node)
	SetLeftChild(node, nodeNewLeft)
	return newRoot

def RotateLeft(node):
	global AVLRoot
	nodeParent = node.Parent
	newRoot = node.RightChild
	nodeNewRight = newRoot.LeftChild
	if nodeParent != 0 and nodeParent.LeftChild == node:
		SetLeftChild(nodeParent, newRoot)
	elif nodeParent != 0 and nodeParent.RightChild == node:
		SetRightChild(nodeParent, newRoot)
	elif nodeParent == 0:
		newRoot.Parent = 0
		AVLRoot = newRoot
	SetLeftChild(newRoot, node)
	SetRightChild(node, nodeNewRight)
	return newRoot

def AVLInsert(key):
	global AVLRoot
	keyParent = AVLRoot
	keyChild = 0
	while True:
		if key < keyParent.Key:
			if keyParent.LeftChild != 0:
				keyParent = keyParent.LeftChild
			else:
				keyChild = Node(key)
				SetLeftChild(keyParent, keyChild)
				break
		elif keyParent.RightChild != 0:
			keyParent = keyParent.RightChild
		else:
			keyChild = Node(key)
			SetRightChild(keyParent, keyChild)
			break
	AVLRebalance(keyParent, keyChild)

def AVLRebalance(parent, child):
	global AVLRoot
	while True:
		if parent.LeftChild == child:
			if parent.BalanceFactor == 1:
				if child.BalanceFactor == -1:
					newCRoot = RotateLeft(child)
					newCRoot.BalanceFactor = 1
					child.BalanceFactor = 0
				newPRoot = RotateRight(parent)
				newPRoot.BalanceFactor = 0
				parent.BalanceFactor = 0
				break
			elif parent.BalanceFactor == -1:
				parent.BalanceFactor = 0
				break
			else:
				parent.BalanceFactor = 1
		elif parent.BalanceFactor == -1:
			if child.BalanceFactor == 1:
				newCRoot = RotateRight(child)
				newCRoot.BalanceFactor = -1
				child.BalanceFactor = 0
			newPRoot = RotateLeft(parent)
			newPRoot.BalanceFactor = 0
			parent.BalanceFactor = 0
			break
		elif parent.BalanceFactor == 1:
			parent.BalanceFactor = 0
			break
		else:
			parent.BalanceFactor = -1
		if parent.Parent == 0:
			break
		else:
			child = child.Parent
			parent = parent.Parent

def AVLSameOrBigger(key):
	global AVLRoot
	curNode = AVLRoot
	candidateExist = False
	bestCandidate = 0
	while curNode != 0:
		if key == curNode.Key:
			candidateExist = True
			bestCandidate = curNode.Key
			break
		elif key < curNode.Key:
			if candidateExist == False:
				candidateExist = True
				bestCandidate = curNode.Key
			else:
				bestCandidate = curNode.Key if curNode.Key - key < bestCandidate - key else bestCandidate
			curNode = curNode.LeftChild
		elif key > curNode.Key:
			curNode = curNode.RightChild
	return (candidateExist, bestCandidate)

def AVLSameOrSmaller(key):
	global AVLRoot
	curNode = AVLRoot
	candidateExist = False
	bestCandidate = 0
	while curNode != 0:
		if key == curNode.Key:
			candidateExist = True
			bestCandidate = curNode.Key
			break
		elif key < curNode.Key:
			curNode = curNode.LeftChild
		elif key > curNode.Key:
			if candidateExist == False:
				candidateExist = True
				bestCandidate = curNode.Key
			else:
				bestCandidate = curNode.Key if key - curNode.Key < key - bestCandidate else bestCandidate
			curNode = curNode.RightChild
	return (candidateExist, bestCandidate)

def PrintTree(node):
	curLevel = [node]
	nextLevel = []
	while len(curLevel) > 0:
		for nd in curLevel:
			if nd == 0:
				print('NULL', end=' ')
			else:
				print((nd.Key, nd.BalanceFactor), end=' ')
				nextLevel.append(nd.LeftChild)
				nextLevel.append(nd.RightChild)
		print()
		curLevel = nextLevel
		nextLevel = []
AVLTree = 0
T = int(input())
for _ in range(T):
	(N, M) = tuple(map(int, input().split()))
	iArr = list(map(int, input().split()))
	sumModArr = [0] * N
	sumModArr[0] = iArr[0]
	for i in range(1, N):
		sumModArr[i] = sumModArr[i - 1] + iArr[i]
	for i in range(N):
		sumModArr[i] = sumModArr[i] % M
	biggestMod = sumModArr[0]
	AVLRoot = Node(sumModArr[0])
	if biggestMod == M - 1:
		print(biggestMod)
		continue
	for i in range(1, N):
		curSumMod = sumModArr[i]
		if curSumMod == M - 1:
			biggestMod = curSumMod
			break
		sameOrBigger = AVLSameOrBigger(curSumMod + 1)
		if sameOrBigger[0] == True and M + curSumMod - sameOrBigger[1] > biggestMod:
			biggestMod = M + curSumMod - sameOrBigger[1]
		if curSumMod > biggestMod:
			biggestMod = curSumMod
		AVLInsert(curSumMod)
	print(biggestMod)


import bisect

def solve(ar, n, m):
	ret = 0
	(prefix, p_len) = ([], 0)
	prev = 0
	for i in range(n):
		cur_mod = ar[i] % m
		cur = (prev + cur_mod) % m
		candidates = [ret, cur]
		i = 0
		if p_len:
			i = bisect.bisect(prefix, cur)
			n_idx = 0 if i == p_len else i
			possible_max = (cur - prefix[n_idx]) % m
			candidates.append(possible_max)
		if i == 0 or (i > 0 and prefix[i - 1] != cur):
			prefix.insert(i, cur)
			p_len += 1
		ret = max(candidates)
		if ret == m - 1:
			return ret
		prev = cur
	return ret
for _ in range(int(input())):
	(n, m) = tuple(map(int, input().split()))
	ar = list(map(int, input().split()))
	print(solve(ar, n, m))


import bisect
testNum = int(input())
for _ in range(testNum):
	(length, M) = [int(num) for num in input().split()]
	nums = [int(num) for num in input().split()]
	ordered = []
	sumMod = 0
	maxMod = 0
	for num in nums:
		sumMod = (sumMod + num) % M
		index = bisect.bisect(ordered, sumMod)
		ordered.insert(index, sumMod)
		maxMod = max(sumMod, maxMod)
		if index + 1 < len(ordered):
			newMod = (ordered[index] - ordered[index + 1]) % M
			maxMod = max(newMod, maxMod)
	print(maxMod)


from array import array
from bisect import bisect_right, insort_right
t = int(input())
for _ in range(t):
	(n, m) = [int(x) for x in input().split()]
	arr = [int(x) for x in input().split()]
	(sub, s) = (array('L'), 0)
	result = 0
	for i in range(n):
		e = arr[i]
		s = (s + e) % m
		j = bisect_right(sub, s)
		if j == i:
			if s > result:
				result = s
		else:
			val = (s - sub[j] + m) % m
			if val > result:
				result = val
		insort_right(sub, s)
	print(result)


import bisect

def maximise_sum(A, N, M):
	B = [0, M]
	S = 0
	V = 0
	for i in range(N):
		V += A[i]
		V %= M
		j = bisect.bisect(B, V)
		S = max(S, (V - B[j] + M) % M)
		B.insert(j, V)
	return S
t = int(input().strip())
for i in range(t):
	nm = [int(x) for x in input().strip().split()]
	ar = [int(y) for y in input().strip().split()]
	print(maximise_sum(ar, nm[0], nm[1]))


import bisect

def maxmod(A, M):
	prefix_sums = [None for i in range(len(A))]
	sorted_prefix_sums = [None]
	prefix_sums[0] = sorted_prefix_sums[0] = A[0] % M
	result = prefix_sums[0]
	for (i, x) in enumerate(A[1:], start=1):
		prefix_sums[i] = (prefix_sums[i - 1] + x % M) % M
		insert_index = bisect.bisect(sorted_prefix_sums, prefix_sums[i])
		bisect.insort(sorted_prefix_sums, prefix_sums[i])
		if insert_index != i:
			max_prefix_sum = (prefix_sums[i] - sorted_prefix_sums[insert_index + 1] + M) % M
		else:
			max_prefix_sum = prefix_sums[i]
		result = max(result, max_prefix_sum)
	return result
for i in range(int(input().strip())):
	(l, m) = [int(x) for x in input().strip().split()]
	arr = [int(x) for x in input().strip().split()]
	print(maxmod(arr, m))


import sys
import bisect

def max_mod(array, M):
	L = [0] * (len(array) + 1)
	for i in range(1, len(L)):
		L[i] = L[i - 1] + array[i - 1]
	acc = 0
	done = []
	for i in range(len(L)):
		x = L[i] % M
		j = bisect.bisect_right(done, x)
		acc = max(acc, x)
		if j < i:
			acc = max(acc, (L[i] - done[j]) % M)
		done.insert(j, x)
	return acc
for _ in range(int(input())):
	(N, M) = input().strip().split()
	(N, M) = [int(N), int(M)]
	array = [int(i) for i in input().strip().split()]
	print(max_mod(array, M))


def f(array, m):
	partial_sums = [0]
	total = 0
	for n in array:
		total = (total + n) % m
		partial_sums.append(total)
	partial_sums = [(x, i) for (i, x) in enumerate(partial_sums)]
	partial_sums.sort()
	(last_n, last_i) = partial_sums[0]
	maximum = 0
	for (x, i) in partial_sums + partial_sums[:1]:
		if x != last_n:
			if last_i > i:
				maximum = max((last_n - x) % m, maximum)
			last_n = x
		last_i = i
	return maximum
T = int(input())
for _ in range(T):
	(n, m) = map(int, input().split())
	array = map(int, input().split())
	print(f(array, m))


import sys
from bisect import bisect_right
__author__ = 'alessandro'

def get_prefix_array(m, a):
	p = [0]
	current = 0
	for e in a:
		current = (e % m + current) % m
		p.append(current)
	return p

def get_max_sum(n, m, a):
	if n == 0:
		return 0
	prefix_array = get_prefix_array(m, a)
	max_sum = 0
	buffer = []
	for (i, p) in enumerate(prefix_array):
		j = bisect_right(buffer, p)
		max_sum = max(max_sum, p)
		if j < i:
			max_sum = max(max_sum, (p - buffer[j]) % m)
		buffer.insert(j, p)
	return max_sum

def main(_):
	num_tests = int(input().strip())
	for _ in range(num_tests):
		(n, m) = map(int, input().strip().split())
		a = [int(x) for x in input().strip().split()]
		print(get_max_sum(n, m, a))
main(sys.argv)


from operator import itemgetter
for T in range(int(input())):
	(N, M) = [int(x) for x in input().split()]
	A = [int(x) for x in input().split()]
	maximum = A[0] % M
	prefix_sums = [(maximum, 1)]
	for i in range(1, N):
		prefix_sums.append(((prefix_sums[i - 1][0] + A[i]) % M, i + 1))
		maximum = max(maximum, prefix_sums[i][0])
	prefix_sums = sorted(prefix_sums, key=itemgetter(0))
	minimum = prefix_sums[-1][0]
	for i in range(N - 1):
		if prefix_sums[i][1] > prefix_sums[i + 1][1]:
			diff = prefix_sums[i + 1][0] - prefix_sums[i][0]
			if diff > 0:
				minimum = min(minimum, diff)
	print(max(maximum, M - minimum))


import bisect
for t in range(int(input())):
	(N, M) = list(map(int, input().split()))
	L = list(map(int, input().split()))
	A = [L[0] % M]
	for i in range(1, len(L)):
		A.append((A[i - 1] + L[i]) % M)
	S = []
	mx = 0
	for i in range(len(A)):
		num = A[i] % M
		mx = max(mx, num)
		j = bisect.bisect_right(S, num)
		if j < i:
			mx = max(mx, (num - S[j]) % M)
		S.insert(j, num)
	print(mx)


import sys
n = int(input().strip())
for _ in range(n):
	(size, mod) = [int(val) for val in input().strip().split(' ')]
	arr = [int(val) for val in input().strip().split(' ')]
	sums = [-1] * size
	temp = [-1] * 2
	temp[0] = arr[0] % mod
	temp[1] = 0
	sums[0] = temp
	for pos in range(1, size):
		temp = [-1] * 2
		temp[0] = (sums[pos - 1][0] + arr[pos] % mod) % mod
		temp[1] = pos
		sums[pos] = temp
	sums = sorted(sums)
	minimum = -1
	for pos in range(0, size - 1):
		if sums[pos][1] > sums[pos + 1][1] and (sums[pos + 1][0] - sums[pos][0] < minimum or minimum == -1):
			minimum = sums[pos + 1][0] - sums[pos][0]
	if sums[size - 1][0] > mod - minimum:
		minimum = mod - sums[size - 1][0]
	print(mod - minimum)


import sys
n = int(input().strip())
for _ in range(n):
	(size, mod) = [int(val) for val in input().strip().split(' ')]
	arr = [int(val) for val in input().strip().split(' ')]
	sums = [-1] * size
	temp = [-1] * 2
	temp[0] = arr[0] % mod
	temp[1] = 0
	sums[0] = temp
	for pos in range(1, size):
		temp = [-1] * 2
		temp[0] = (sums[pos - 1][0] + arr[pos] % mod) % mod
		temp[1] = pos
		sums[pos] = temp
	sums = sorted(sums)
	minimum = -1
	for pos in range(0, size - 1):
		if sums[pos][1] > sums[pos + 1][1] and (sums[pos + 1][0] - sums[pos][0] < minimum or minimum == -1):
			minimum = sums[pos + 1][0] - sums[pos][0]
	if sums[size - 1][0] > mod - minimum:
		minimum = mod - sums[size - 1][0]
	print(mod - minimum)


import bisect
tests = int(input())
for test in range(tests):
	(N, M) = tuple(map(int, input().split()))
	arr = list(map(lambda x: int(x) % M, input().split()))
	acc = [arr[0]]
	for n in arr[1:]:
		acc.append((acc[-1] + n) % M)
	pre = []
	ans = 0
	for n in acc:
		pos = bisect.bisect(pre, n)
		if len(pre) == pos:
			ans = max(ans, n)
		else:
			ans = max(ans, (n + M - pre[pos]) % M)
		bisect.insort(pre, n)
	print(ans)


import sys
n = int(input().strip())
for _ in range(n):
	(size, mod) = [int(val) for val in input().strip().split(' ')]
	arr = [int(val) for val in input().strip().split(' ')]
	sums = [-1] * size
	temp = [-1] * 2
	temp[0] = arr[0] % mod
	temp[1] = 0
	sums[0] = temp
	for pos in range(1, size):
		temp = [-1] * 2
		temp[0] = (sums[pos - 1][0] + arr[pos] % mod) % mod
		temp[1] = pos
		sums[pos] = temp
	sums = sorted(sums)
	minimum = -1
	for pos in range(0, size - 1):
		if sums[pos][1] > sums[pos + 1][1] and (sums[pos + 1][0] - sums[pos][0] < minimum or minimum == -1):
			minimum = sums[pos + 1][0] - sums[pos][0]
	if sums[size - 1][0] > mod - minimum:
		minimum = mod - sums[size - 1][0]
	print(mod - minimum)


import bisect

def scanl(f, base, l):
	for x in l:
		base = f(base, x)
		yield base

def solve(m, es):
	ms = tuple(scanl(lambda a, b: (a + b) % m, 0, es))
	pre_sum = []
	max_value = 0
	for n in ms:
		max_value = max(max_value, n)
		pos = bisect.bisect_right(pre_sum, n)
		if pos < len(pre_sum):
			max_value = max(max_value, n - pre_sum[pos] + m)
		bisect.insort_right(pre_sum, n)
	return max_value

def main():
	T = int(input())
	for _ in range(T):
		(N, M) = tuple((int(v) for v in input().split()))
		ES = tuple((int(v) for v in input().split()))
		print(solve(M, ES))
main()


n = int(input().strip())
for _ in range(n):
	(size, mod) = [int(val) for val in input().strip().split(' ')]
	arr = [int(val) for val in input().strip().split(' ')]
	sums = [-1] * size
	temp = [-1] * 2
	temp[0] = arr[0] % mod
	temp[1] = 0
	sums[0] = temp
	for pos in range(1, size):
		temp = [-1] * 2
		temp[0] = (sums[pos - 1][0] + arr[pos] % mod) % mod
		temp[1] = pos
		sums[pos] = temp
	sums = sorted(sums)
	minimum = -1
	for pos in range(0, size - 1):
		if sums[pos][1] > sums[pos + 1][1] and (sums[pos + 1][0] - sums[pos][0] < minimum or minimum == -1):
			minimum = sums[pos + 1][0] - sums[pos][0]
	if sums[size - 1][0] > mod - minimum:
		minimum = mod - sums[size - 1][0]
	print(mod - minimum)


import sys
n = int(input().strip())
for _ in range(n):
	(size, mod) = [int(val) for val in input().strip().split(' ')]
	arr = [int(val) for val in input().strip().split(' ')]
	sums = [-1] * size
	temp = [-1] * 2
	temp[0] = arr[0] % mod
	temp[1] = 0
	sums[0] = temp
	for pos in range(1, size):
		temp = [-1] * 2
		temp[0] = (sums[pos - 1][0] + arr[pos] % mod) % mod
		temp[1] = pos
		sums[pos] = temp
	sums = sorted(sums)
	minimum = -1
	for pos in range(0, size - 1):
		if sums[pos][1] > sums[pos + 1][1] and (sums[pos + 1][0] - sums[pos][0] < minimum or minimum == -1):
			minimum = sums[pos + 1][0] - sums[pos][0]
	if sums[size - 1][0] > mod - minimum:
		minimum = mod - sums[size - 1][0]
	print(mod - minimum)


import sys
n = int(input().strip())
for _ in range(n):
	(size, mod) = [int(val) for val in input().strip().split(' ')]
	arr = [int(val) for val in input().strip().split(' ')]
	sums = [-1] * size
	temp = [-1] * 2
	temp[0] = arr[0] % mod
	temp[1] = 0
	sums[0] = temp
	for pos in range(1, size):
		temp = [-1] * 2
		temp[0] = (sums[pos - 1][0] + arr[pos] % mod) % mod
		temp[1] = pos
		sums[pos] = temp
	sums = sorted(sums)
	minimum = -1
	for pos in range(0, size - 1):
		if sums[pos][1] > sums[pos + 1][1] and (sums[pos + 1][0] - sums[pos][0] < minimum or minimum == -1):
			minimum = sums[pos + 1][0] - sums[pos][0]
	if sums[size - 1][0] > mod - minimum:
		minimum = mod - sums[size - 1][0]
	print(mod - minimum)


from bisect import bisect_right
for _ in range(int(input())):
	(n, m) = map(int, input().split())
	a = list(map(int, input().split()))
	l = []
	su = 0
	r = 0
	for i in range(n):
		su += a[i]
		su %= m
		it = bisect_right(l, su)
		if it != len(l):
			r = max(r, su - l[it] + m)
			l.insert(it, su)
		else:
			r = max(r, su)
			l.append(su)
	print(r)


def Solve():
	(N, M) = map(int, input().split())
	data = list(map(int, input().split()))
	computed = []
	prevS = 0
	for i in range(N):
		prevS = (prevS + data[i]) % M
		computed.append((prevS, i))
	minS = -1
	computed = sorted(computed)
	for i in range(N - 1):
		if computed[i][1] > computed[i + 1][1] and (minS == -1 or minS > computed[i + 1][0] - computed[i][0]):
			minS = computed[i + 1][0] - computed[i][0]
	print(max(computed[N - 1][0], M - minS))
for _ in range(int(input())):
	Solve()


class MaximizeSum:

	def __init__(self):
		(_, self.mod) = get_int_list(input())
		str_input = input()
		self.values = []
		self.cum_sums = []
		self.running_max = 0
		for (i, val) in enumerate(str_input.strip().split()):
			val_int = int(val) % self.mod
			self.values.append(val_int)

	def calculate(self):
		cum_sums = []
		cum_val = 0
		for (i, val) in enumerate(self.values):
			cum_val = (cum_val + val) % self.mod
			cum_sums.append((cum_val, i))
		cum_sums.sort()
		min_val = self.mod
		for i in range(len(cum_sums) - 1):
			(value_this, index_this) = cum_sums[i]
			(value_next, index_next) = cum_sums[i + 1]
			if index_this > index_next:
				this_min = value_next - value_this
				min_val = min(this_min, min_val)
		result = max(cum_sums[len(cum_sums) - 1][0], self.mod - min_val)
		return result

def main():
	cases = int(input())
	for _ in range(cases):
		my_obj = MaximizeSum()
		print(my_obj.calculate())

def get_int_list(in_str):
	return [int(i) for i in in_str.strip().split()]
main()


import sys
n = int(input().strip())
for _ in range(n):
	(size, mod) = [int(val) for val in input().strip().split(' ')]
	arr = [int(val) for val in input().strip().split(' ')]
	sums = [-1] * size
	temp = [-1] * 2
	temp[0] = arr[0] % mod
	temp[1] = 0
	sums[0] = temp
	for pos in range(1, size):
		temp = [-1] * 2
		temp[0] = (sums[pos - 1][0] + arr[pos] % mod) % mod
		temp[1] = pos
		sums[pos] = temp
	sums = sorted(sums)
	minimum = -1
	for pos in range(0, size - 1):
		if sums[pos][1] > sums[pos + 1][1] and (sums[pos + 1][0] - sums[pos][0] < minimum or minimum == -1):
			minimum = sums[pos + 1][0] - sums[pos][0]
	if sums[size - 1][0] > mod - minimum:
		minimum = mod - sums[size - 1][0]
	print(mod - minimum)


def main_solve():
	M = int(input().split()[1])
	num = list(map(int, input().split()))
	prefix = []
	sum = 0
	for n in num:
		prefix.append((sum + n) % M)
		sum += n
	prefix_index = [(i, prefix[i]) for i in range(len(num))]
	prefix_index.sort(key=lambda x: x[1])
	min_diff = M
	for i in range(len(num) - 1):
		this = prefix_index[i][1]
		next = prefix_index[i + 1][1]
		this_index = prefix_index[i][0]
		next_index = prefix_index[i + 1][0]
		if next - this < min_diff and next != this and (this_index > next_index):
			min_diff = next - this
	print(max(M - min_diff, max(prefix)))
_tt = int(input())
for _ in range(_tt):
	main_solve()


import sys
n = int(input().strip())
for _ in range(n):
	(size, mod) = [int(val) for val in input().strip().split(' ')]
	arr = [int(val) for val in input().strip().split(' ')]
	sums = [-1] * size
	temp = [-1] * 2
	temp[0] = arr[0] % mod
	temp[1] = 0
	sums[0] = temp
	for pos in range(1, size):
		temp = [-1] * 2
		temp[0] = (sums[pos - 1][0] + arr[pos] % mod) % mod
		temp[1] = pos
		sums[pos] = temp
	sums = sorted(sums)
	minimum = -1
	for pos in range(0, size - 1):
		if sums[pos][1] > sums[pos + 1][1] and (sums[pos + 1][0] - sums[pos][0] < minimum or minimum == -1):
			minimum = sums[pos + 1][0] - sums[pos][0]
	if sums[size - 1][0] > mod - minimum:
		minimum = mod - sums[size - 1][0]
	print(mod - minimum)


import sys
n = int(input().strip())
for _ in range(n):
	(size, mod) = [int(val) for val in input().strip().split(' ')]
	arr = [int(val) for val in input().strip().split(' ')]
	sums = [-1] * size
	temp = [-1] * 2
	temp[0] = arr[0] % mod
	temp[1] = 0
	sums[0] = temp
	for pos in range(1, size):
		temp = [-1] * 2
		temp[0] = (sums[pos - 1][0] + arr[pos] % mod) % mod
		temp[1] = pos
		sums[pos] = temp
	sums = sorted(sums)
	minimum = -1
	for pos in range(0, size - 1):
		if sums[pos][1] > sums[pos + 1][1] and (sums[pos + 1][0] - sums[pos][0] < minimum or minimum == -1):
			minimum = sums[pos + 1][0] - sums[pos][0]
	if sums[size - 1][0] > mod - minimum:
		minimum = mod - sums[size - 1][0]
	print(mod - minimum)


import sys
n = int(input().strip())
for _ in range(n):
	(size, mod) = [int(val) for val in input().strip().split(' ')]
	arr = [int(val) for val in input().strip().split(' ')]
	sums = [-1] * size
	temp = [-1] * 2
	temp[0] = arr[0] % mod
	temp[1] = 0
	sums[0] = temp
	for pos in range(1, size):
		temp = [-1] * 2
		temp[0] = (sums[pos - 1][0] + arr[pos] % mod) % mod
		temp[1] = pos
		sums[pos] = temp
	sums = sorted(sums)
	minimum = -1
	for pos in range(0, size - 1):
		if sums[pos][1] > sums[pos + 1][1] and (sums[pos + 1][0] - sums[pos][0] < minimum or minimum == -1):
			minimum = sums[pos + 1][0] - sums[pos][0]
	if sums[size - 1][0] > mod - minimum:
		minimum = mod - sums[size - 1][0]
	print(mod - minimum)


import sys
n = int(input().strip())
for _ in range(n):
	(size, mod) = [int(val) for val in input().strip().split(' ')]
	arr = [int(val) for val in input().strip().split(' ')]
	sums = [-1] * size
	temp = [-1] * 2
	temp[0] = arr[0] % mod
	temp[1] = 0
	sums[0] = temp
	for pos in range(1, size):
		temp = [-1] * 2
		temp[0] = (sums[pos - 1][0] + arr[pos] % mod) % mod
		temp[1] = pos
		sums[pos] = temp
	sums = sorted(sums)
	minimum = -1
	for pos in range(0, size - 1):
		if sums[pos][1] > sums[pos + 1][1] and (sums[pos + 1][0] - sums[pos][0] < minimum or minimum == -1):
			minimum = sums[pos + 1][0] - sums[pos][0]
	if sums[size - 1][0] > mod - minimum:
		minimum = mod - sums[size - 1][0]
	print(mod - minimum)


import sys
n = int(input().strip())
for _ in range(n):
	(size, mod) = [int(val) for val in input().strip().split(' ')]
	arr = [int(val) for val in input().strip().split(' ')]
	sums = [-1] * size
	temp = [-1] * 2
	temp[0] = arr[0] % mod
	temp[1] = 0
	sums[0] = temp
	for pos in range(1, size):
		temp = [-1] * 2
		temp[0] = (sums[pos - 1][0] + arr[pos] % mod) % mod
		temp[1] = pos
		sums[pos] = temp
	sums = sorted(sums)
	minimum = -1
	for pos in range(0, size - 1):
		if sums[pos][1] > sums[pos + 1][1] and (sums[pos + 1][0] - sums[pos][0] < minimum or minimum == -1):
			minimum = sums[pos + 1][0] - sums[pos][0]
	if sums[size - 1][0] > mod - minimum:
		minimum = mod - sums[size - 1][0]
	print(mod - minimum)


t = int(input())
size = [None] * t
mod = [None] * t
result = [None] * t
for i in range(t):
	n_m = input()
	n_m = n_m.split()
	size[i] = int(n_m[0])
	mod[i] = int(n_m[1])
	arr = input()
	arr = arr.split()
	arr = [int(x) for x in arr]
	prefix_arr = []
	current = result[i] = 0
	for (j, x) in enumerate(arr):
		current = (x % mod[i] + current) % mod[i]
		prefix_arr.append(current)
		if current > result[i]:
			result[i] = current
	ind = sorted(range(size[i]), key=lambda k: prefix_arr[k])
	prefix_arr = sorted(prefix_arr)
	temp = 0
	for j in range(size[i] - 1):
		if ind[j] > ind[j + 1]:
			temp = max(temp, (prefix_arr[j] - prefix_arr[j + 1] + mod[i]) % mod[i])
	result[i] = max(result[i], temp)
for x in result:
	print(x)


import sys
n = int(input().strip())
for _ in range(n):
	(size, mod) = [int(val) for val in input().strip().split(' ')]
	arr = [int(val) for val in input().strip().split(' ')]
	sums = [-1] * size
	temp = [-1] * 2
	temp[0] = arr[0] % mod
	temp[1] = 0
	sums[0] = temp
	for pos in range(1, size):
		temp = [-1] * 2
		temp[0] = (sums[pos - 1][0] + arr[pos] % mod) % mod
		temp[1] = pos
		sums[pos] = temp
	sums = sorted(sums)
	minimum = -1
	for pos in range(0, size - 1):
		if sums[pos][1] > sums[pos + 1][1] and (sums[pos + 1][0] - sums[pos][0] < minimum or minimum == -1):
			minimum = sums[pos + 1][0] - sums[pos][0]
	if sums[size - 1][0] > mod - minimum:
		minimum = mod - sums[size - 1][0]
	print(mod - minimum)


import bisect
t = int(input())
for i in range(t):
	(n, m) = map(int, input().split())
	a = list(map(int, input().split()))
	sum = [a[0] % m]
	for x in a[1:]:
		sum.append((sum[-1] + x) % m)
	seen = [0]
	mx = -1
	for s in sum:
		idx = bisect.bisect_left(seen, s)
		if idx < len(seen):
			mx = max(mx, s, (s - seen[idx]) % m)
		else:
			mx = max(mx, s)
		bisect.insort_left(seen, s)
	print(mx)


import sys
n = int(input().strip())
for _ in range(n):
	(size, mod) = [int(val) for val in input().strip().split(' ')]
	arr = [int(val) for val in input().strip().split(' ')]
	sums = [-1] * size
	temp = [-1] * 2
	temp[0] = arr[0] % mod
	temp[1] = 0
	sums[0] = temp
	for pos in range(1, size):
		temp = [-1] * 2
		temp[0] = (sums[pos - 1][0] + arr[pos] % mod) % mod
		temp[1] = pos
		sums[pos] = temp
	sums = sorted(sums)
	minimum = -1
	for pos in range(0, size - 1):
		if sums[pos][1] > sums[pos + 1][1] and (sums[pos + 1][0] - sums[pos][0] < minimum or minimum == -1):
			minimum = sums[pos + 1][0] - sums[pos][0]
	if sums[size - 1][0] > mod - minimum:
		minimum = mod - sums[size - 1][0]
	print(mod - minimum)


import sys
t = int(input().strip())
for _ in range(t):
	(size, mod) = [int(val) for val in input().strip().split(' ')]
	arr = [int(val) for val in input().strip().split(' ')]
	sums = [-1] * size
	temp = [-1] * 2
	temp[0] = arr[0] % mod
	temp[1] = 0
	sums[0] = temp
	for pos in range(1, size):
		temp = [-1] * 2
		temp[0] = (sums[pos - 1][0] + arr[pos] % mod) % mod
		temp[1] = pos
		sums[pos] = temp
	sums = sorted(sums)
	minimum = -1
	for pos in range(0, size - 1):
		if sums[pos][1] > sums[pos + 1][1] and (sums[pos + 1][0] - sums[pos][0] < minimum or minimum == -1):
			minimum = sums[pos + 1][0] - sums[pos][0]
	if sums[size - 1][0] > mod - minimum:
		minimum = mod - sums[size - 1][0]
	print(mod - minimum)


def mod_M(x, M):
	return x - M * (x // M)
t = int(input(''))
for each in range(t):
	(N, M) = input('').split()
	(N, M) = (int(N), int(M))
	s = [(0, 0) for i in range(N + 1)]
	inp = input('').split()
	inp = [int(num) for num in inp]
	for i in range(1, N + 1):
		s[i] = (mod_M(s[i - 1][0] + inp[i - 1], M), i)
	s.sort()
	finished = False
	ans = 0
	for i in range(1, N + 1):
		if s[i - 1][1] > s[i][1]:
			ans = max(ans, mod_M(s[i - 1][0] - s[i][0], M))
	ans = max(ans, s[-1][0])
	print(ans)


import sys
n = int(input().strip())
for _ in range(n):
	(size, mod) = [int(val) for val in input().strip().split(' ')]
	arr = [int(val) for val in input().strip().split(' ')]
	sums = [-1] * size
	temp = [-1] * 2
	temp[0] = arr[0] % mod
	temp[1] = 0
	sums[0] = temp
	for pos in range(1, size):
		temp = [-1] * 2
		temp[0] = (sums[pos - 1][0] + arr[pos] % mod) % mod
		temp[1] = pos
		sums[pos] = temp
	sums = sorted(sums)
	minimum = -1
	for pos in range(0, size - 1):
		if sums[pos][1] > sums[pos + 1][1] and (sums[pos + 1][0] - sums[pos][0] < minimum or minimum == -1):
			minimum = sums[pos + 1][0] - sums[pos][0]
	if sums[size - 1][0] > mod - minimum:
		minimum = mod - sums[size - 1][0]
	print(mod - minimum)


import sys
n = int(input().strip())
for _ in range(n):
	(size, mod) = [int(val) for val in input().strip().split(' ')]
	arr = [int(val) for val in input().strip().split(' ')]
	sums = [-1] * size
	temp = [-1] * 2
	temp[0] = arr[0] % mod
	temp[1] = 0
	sums[0] = temp
	for pos in range(1, size):
		temp = [-1] * 2
		temp[0] = (sums[pos - 1][0] + arr[pos] % mod) % mod
		temp[1] = pos
		sums[pos] = temp
	sums = sorted(sums)
	minimum = -1
	for pos in range(0, size - 1):
		if sums[pos][1] > sums[pos + 1][1] and (sums[pos + 1][0] - sums[pos][0] < minimum or minimum == -1):
			minimum = sums[pos + 1][0] - sums[pos][0]
	if sums[size - 1][0] > mod - minimum:
		minimum = mod - sums[size - 1][0]
	print(mod - minimum)


import sys
n = int(input().strip())
for _ in range(n):
	(size, mod) = [int(val) for val in input().strip().split(' ')]
	arr = [int(val) for val in input().strip().split(' ')]
	sums = [-1] * size
	temp = [-1] * 2
	temp[0] = arr[0] % mod
	temp[1] = 0
	sums[0] = temp
	for pos in range(1, size):
		temp = [-1] * 2
		temp[0] = (sums[pos - 1][0] + arr[pos] % mod) % mod
		temp[1] = pos
		sums[pos] = temp
	sums = sorted(sums)
	minimum = -1
	for pos in range(0, size - 1):
		if sums[pos][1] > sums[pos + 1][1] and (sums[pos + 1][0] - sums[pos][0] < minimum or minimum == -1):
			minimum = sums[pos + 1][0] - sums[pos][0]
	if sums[size - 1][0] > mod - minimum:
		minimum = mod - sums[size - 1][0]
	print(mod - minimum)


import sys
n = int(input().strip())
for _ in range(n):
	(size, mod) = [int(val) for val in input().strip().split(' ')]
	arr = [int(val) for val in input().strip().split(' ')]
	sums = [-1] * size
	temp = [-1] * 2
	temp[0] = arr[0] % mod
	temp[1] = 0
	sums[0] = temp
	for pos in range(1, size):
		temp = [-1] * 2
		temp[0] = (sums[pos - 1][0] + arr[pos] % mod) % mod
		temp[1] = pos
		sums[pos] = temp
	sums = sorted(sums)
	minimum = -1
	for pos in range(0, size - 1):
		if sums[pos][1] > sums[pos + 1][1] and (sums[pos + 1][0] - sums[pos][0] < minimum or minimum == -1):
			minimum = sums[pos + 1][0] - sums[pos][0]
	if sums[size - 1][0] > mod - minimum:
		minimum = mod - sums[size - 1][0]
	print(mod - minimum)


from itertools import accumulate
t = int(input())
for i in range(t):
	(n, m) = map(int, input().split())
	l = list(map(int, input().split()))
	pref = [0] * n
	pref[0] = l[0] % m
	mx = pref[0]
	for i in range(1, n):
		pref[i] = (l[i] + pref[i - 1]) % m
		mx = max(mx, pref[i])
	tup = []
	for i in range(n):
		tup.append((pref[i], i))
	tup.sort()
	mn = 10 ** 14
	for i in range(n - 1):
		if tup[i][1] > tup[i + 1][1]:
			mn = min(mn, tup[i + 1][0] - tup[i][0])
	print(max(mx, m - mn))


def fast_max(arr, m, arr_len):
	maxx = 0
	cumu = 0
	cumu_mo = []
	for i in range(arr_len):
		cumu += arr[i]
		n = cumu % m
		cumu_mo.append(n)
		if n > maxx:
			maxx = n
	idx_arr = sorted(range(len(cumu_mo)), key=lambda k: cumu_mo[k])
	min_diff = m
	for i in range(len(cumu_mo) - 1):
		diff = cumu_mo[idx_arr[i + 1]] - cumu_mo[idx_arr[i]]
		if diff != 0 and diff < min_diff and (idx_arr[i + 1] < idx_arr[i]):
			min_diff = diff
			if m - diff > maxx:
				maxx = m - diff
	return maxx
cases = int(input().strip())
for i in range(cases):
	(l, m) = input().strip().split(' ')
	arr = [int(x) for x in input().strip().split(' ')]
	print(fast_max(arr, int(m), int(l)))


import sys
n = int(input().strip())
for _ in range(n):
	(size, mod) = [int(val) for val in input().strip().split(' ')]
	arr = [int(val) for val in input().strip().split(' ')]
	sums = [-1] * size
	temp = [-1] * 2
	temp[0] = arr[0] % mod
	temp[1] = 0
	sums[0] = temp
	for pos in range(1, size):
		temp = [-1] * 2
		temp[0] = (sums[pos - 1][0] + arr[pos] % mod) % mod
		temp[1] = pos
		sums[pos] = temp
	sums = sorted(sums)
	minimum = -1
	for pos in range(0, size - 1):
		if sums[pos][1] > sums[pos + 1][1] and (sums[pos + 1][0] - sums[pos][0] < minimum or minimum == -1):
			minimum = sums[pos + 1][0] - sums[pos][0]
	if sums[size - 1][0] > mod - minimum:
		minimum = mod - sums[size - 1][0]
	print(mod - minimum)


import sys
n = int(input().strip())
for _ in range(n):
	(size, mod) = [int(val) for val in input().strip().split(' ')]
	arr = [int(val) for val in input().strip().split(' ')]
	sums = [-1] * size
	temp = [-1] * 2
	temp[0] = arr[0] % mod
	temp[1] = 0
	sums[0] = temp
	for pos in range(1, size):
		temp = [-1] * 2
		temp[0] = (sums[pos - 1][0] + arr[pos] % mod) % mod
		temp[1] = pos
		sums[pos] = temp
	sums = sorted(sums)
	minimum = -1
	for pos in range(0, size - 1):
		if sums[pos][1] > sums[pos + 1][1] and (sums[pos + 1][0] - sums[pos][0] < minimum or minimum == -1):
			minimum = sums[pos + 1][0] - sums[pos][0]
	if sums[size - 1][0] > mod - minimum:
		minimum = mod - sums[size - 1][0]
	print(mod - minimum)


import sys
n = int(input().strip())
for _ in range(n):
	(size, mod) = [int(val) for val in input().strip().split(' ')]
	arr = [int(val) for val in input().strip().split(' ')]
	sums = [-1] * size
	temp = [-1] * 2
	temp[0] = arr[0] % mod
	temp[1] = 0
	sums[0] = temp
	for pos in range(1, size):
		temp = [-1] * 2
		temp[0] = (sums[pos - 1][0] + arr[pos] % mod) % mod
		temp[1] = pos
		sums[pos] = temp
	sums = sorted(sums)
	minimum = -1
	for pos in range(0, size - 1):
		if sums[pos][1] > sums[pos + 1][1] and (sums[pos + 1][0] - sums[pos][0] < minimum or minimum == -1):
			minimum = sums[pos + 1][0] - sums[pos][0]
	if sums[size - 1][0] > mod - minimum:
		minimum = mod - sums[size - 1][0]
	print(mod - minimum)


t = int(input())
for i in range(t):
	(n, m) = list(map(int, input().split()))
	ar = list(map(int, input().split()))
	prefix_sum = []
	tem = 0
	max_i = 0
	l = len(ar)
	for j in range(l):
		prefix_sum.append(tem + ar[j])
		tem = tem + ar[j]
	ps = []
	for j in range(l):
		prefix_sum[j] = prefix_sum[j] % m
		ps.append((prefix_sum[j], j))
	ps = sorted(ps, key=lambda x: x[0])
	for j in range(l - 1):
		if ps[j][1] > ps[j + 1][1]:
			max_i = max((ps[j][0] - ps[j + 1][0] + m) % m, max_i)
		max_i = max(max_i, ps[j][0])
	max_i = max(max_i, ps[l - 1][0])
	print(max_i)


t = int(input())
for _ in range(t):
	(n, mod) = map(int, input().split())
	x = input().split()
	value = []
	index = []
	temp = 0
	for i in range(n):
		temp += int(x[i])
		value.append(temp % mod)
		index.append(i + 1)
	aa = []
	for x in zip(*sorted(zip(value, index))):
		aa.append(list(x))
	value = aa[0]
	index = aa[1]
	ans = 1000000000000000000000
	for i in range(n - 1):
		if value[i] < value[i + 1] and index[i] > index[i + 1]:
			ans = min(ans, value[i + 1] - value[i])
	print(max(max(value), mod - ans))


import sys
n = int(input().strip())
for i in range(n):
	(size, mod) = [int(temp) for temp in input().strip().split(' ')]
	arr = [int(temp) for temp in input().strip().split(' ')]
	sums = [-1] * size
	temp = [-1] * 2
	temp[0] = arr[0] % mod
	temp[1] = 0
	sums[0] = temp
	for j in range(1, size):
		temp = [-1] * 2
		temp[0] = (sums[j - 1][0] + arr[j] % mod) % mod
		temp[1] = j
		sums[j] = temp
	sums = sorted(sums)
	minimum = -1
	for j in range(0, size - 1):
		if sums[j][1] > sums[j + 1][1] and (sums[j + 1][0] - sums[j][0] < minimum or minimum == -1):
			minimum = sums[j + 1][0] - sums[j][0]
	if sums[size - 1][0] > mod - minimum:
		minimum = mod - sums[size - 1][0]
	print(mod - minimum)


import sys
n = int(input().strip())
for _ in range(n):
	(size, mod) = [int(val) for val in input().strip().split(' ')]
	arr = [int(val) for val in input().strip().split(' ')]
	sums = [-1] * size
	temp = [-1] * 2
	temp[0] = arr[0] % mod
	temp[1] = 0
	sums[0] = temp
	for pos in range(1, size):
		temp = [-1] * 2
		temp[0] = (sums[pos - 1][0] + arr[pos] % mod) % mod
		temp[1] = pos
		sums[pos] = temp
	sums = sorted(sums)
	minimum = -1
	for pos in range(0, size - 1):
		if sums[pos][1] > sums[pos + 1][1] and (sums[pos + 1][0] - sums[pos][0] < minimum or minimum == -1):
			minimum = sums[pos + 1][0] - sums[pos][0]
	if sums[size - 1][0] > mod - minimum:
		minimum = mod - sums[size - 1][0]
	print(mod - minimum)


import sys
n = int(input().strip())
for _ in range(n):
	(size, mod) = [int(val) for val in input().strip().split(' ')]
	arr = [int(val) for val in input().strip().split(' ')]
	sums = [-1] * size
	temp = [-1] * 2
	temp[0] = arr[0] % mod
	temp[1] = 0
	sums[0] = temp
	for pos in range(1, size):
		temp = [-1] * 2
		temp[0] = (sums[pos - 1][0] + arr[pos] % mod) % mod
		temp[1] = pos
		sums[pos] = temp
	sums = sorted(sums)
	minimum = -1
	for pos in range(0, size - 1):
		if sums[pos][1] > sums[pos + 1][1] and (sums[pos + 1][0] - sums[pos][0] < minimum or minimum == -1):
			minimum = sums[pos + 1][0] - sums[pos][0]
	if sums[size - 1][0] > mod - minimum:
		minimum = mod - sums[size - 1][0]
	print(mod - minimum)


import sys
n = int(input().strip())
for _ in range(n):
	(size, mod) = [int(val) for val in input().strip().split(' ')]
	arr = [int(val) for val in input().strip().split(' ')]
	sums = [-1] * size
	temp = [-1] * 2
	temp[0] = arr[0] % mod
	temp[1] = 0
	sums[0] = temp
	for pos in range(1, size):
		temp = [-1] * 2
		temp[0] = (sums[pos - 1][0] + arr[pos] % mod) % mod
		temp[1] = pos
		sums[pos] = temp
	sums = sorted(sums)
	minimum = -1
	for pos in range(0, size - 1):
		if sums[pos][1] > sums[pos + 1][1] and (sums[pos + 1][0] - sums[pos][0] < minimum or minimum == -1):
			minimum = sums[pos + 1][0] - sums[pos][0]
	if sums[size - 1][0] > mod - minimum:
		minimum = mod - sums[size - 1][0]
	print(mod - minimum)


import sys
n = int(input().strip())
for _ in range(n):
	(size, mod) = [int(val) for val in input().strip().split(' ')]
	arr = [int(val) for val in input().strip().split(' ')]
	sums = [-1] * size
	temp = [-1] * 2
	temp[0] = arr[0] % mod
	temp[1] = 0
	sums[0] = temp
	for pos in range(1, size):
		temp = [-1] * 2
		temp[0] = (sums[pos - 1][0] + arr[pos] % mod) % mod
		temp[1] = pos
		sums[pos] = temp
	sums = sorted(sums)
	minimum = -1
	for pos in range(0, size - 1):
		if sums[pos][1] > sums[pos + 1][1] and (sums[pos + 1][0] - sums[pos][0] < minimum or minimum == -1):
			minimum = sums[pos + 1][0] - sums[pos][0]
	if sums[size - 1][0] > mod - minimum:
		minimum = mod - sums[size - 1][0]
	print(mod - minimum)


import sys
n = int(input().strip())
for _ in range(n):
	(size, mod) = [int(val) for val in input().strip().split(' ')]
	arr = [int(val) for val in input().strip().split(' ')]
	sums = [-1] * size
	temp = [-1] * 2
	temp[0] = arr[0] % mod
	temp[1] = 0
	sums[0] = temp
	for pos in range(1, size):
		temp = [-1] * 2
		temp[0] = (sums[pos - 1][0] + arr[pos] % mod) % mod
		temp[1] = pos
		sums[pos] = temp
	sums = sorted(sums)
	minimum = -1
	for pos in range(0, size - 1):
		if sums[pos][1] > sums[pos + 1][1] and (sums[pos + 1][0] - sums[pos][0] < minimum or minimum == -1):
			minimum = sums[pos + 1][0] - sums[pos][0]
	if sums[size - 1][0] > mod - minimum:
		minimum = mod - sums[size - 1][0]
	print(mod - minimum)


import sys
n = int(input().strip())
for _ in range(n):
	(size, mod) = [int(val) for val in input().strip().split(' ')]
	arr = [int(val) for val in input().strip().split(' ')]
	sums = [-1] * size
	temp = [-1] * 2
	temp[0] = arr[0] % mod
	temp[1] = 0
	sums[0] = temp
	for pos in range(1, size):
		temp = [-1] * 2
		temp[0] = (sums[pos - 1][0] + arr[pos] % mod) % mod
		temp[1] = pos
		sums[pos] = temp
	sums = sorted(sums)
	minimum = -1
	for pos in range(0, size - 1):
		if sums[pos][1] > sums[pos + 1][1] and (sums[pos + 1][0] - sums[pos][0] < minimum or minimum == -1):
			minimum = sums[pos + 1][0] - sums[pos][0]
	if sums[size - 1][0] > mod - minimum:
		minimum = mod - sums[size - 1][0]
	print(mod - minimum)


import sys
n = int(input().strip())
for _ in range(n):
	(size, mod) = [int(val) for val in input().strip().split(' ')]
	arr = [int(val) for val in input().strip().split(' ')]
	sums = [-1] * size
	temp = [-1] * 2
	temp[0] = arr[0] % mod
	temp[1] = 0
	sums[0] = temp
	for pos in range(1, size):
		temp = [-1] * 2
		temp[0] = (sums[pos - 1][0] + arr[pos] % mod) % mod
		temp[1] = pos
		sums[pos] = temp
	sums = sorted(sums)
	minimum = -1
	for pos in range(0, size - 1):
		if sums[pos][1] > sums[pos + 1][1] and (sums[pos + 1][0] - sums[pos][0] < minimum or minimum == -1):
			minimum = sums[pos + 1][0] - sums[pos][0]
	if sums[size - 1][0] > mod - minimum:
		minimum = mod - sums[size - 1][0]
	print(mod - minimum)


import bisect
T = int(input().strip())
for _ in range(T):
	(n, m) = map(int, input().strip().split())
	L = list(map(int, input().strip().split()))
	sum = [L[0] % m]
	tree = []
	bisect.insort(tree, sum[0])
	result = sum[0]
	for i in range(1, n):
		sum.append((sum[i - 1] + L[i]) % m)
		j = bisect.bisect_right(tree, sum[i])
		if j >= len(tree):
			result = max(sum[i] % m, result)
			bisect.insort(tree, sum[i])
		else:
			result = max((sum[i] - tree[j] + m) % m, result)
			bisect.insort(tree, sum[i])
	print(result)


import sys
n = int(input().strip())
for _ in range(n):
	(size, mod) = [int(val) for val in input().strip().split(' ')]
	arr = [int(val) for val in input().strip().split(' ')]
	sums = [-1] * size
	temp = [-1] * 2
	temp[0] = arr[0] % mod
	temp[1] = 0
	sums[0] = temp
	for pos in range(1, size):
		temp = [-1] * 2
		temp[0] = (sums[pos - 1][0] + arr[pos] % mod) % mod
		temp[1] = pos
		sums[pos] = temp
	sums = sorted(sums)
	minimum = -1
	for pos in range(0, size - 1):
		if sums[pos][1] > sums[pos + 1][1] and (sums[pos + 1][0] - sums[pos][0] < minimum or minimum == -1):
			minimum = sums[pos + 1][0] - sums[pos][0]
	if sums[size - 1][0] > mod - minimum:
		minimum = mod - sums[size - 1][0]
	print(mod - minimum)


import sys
n = int(input().strip())
for _ in range(n):
	(size, mod) = [int(val) for val in input().strip().split(' ')]
	arr = [int(val) for val in input().strip().split(' ')]
	sums = [-1] * size
	temp = [-1] * 2
	temp[0] = arr[0] % mod
	temp[1] = 0
	sums[0] = temp
	for pos in range(1, size):
		temp = [-1] * 2
		temp[0] = (sums[pos - 1][0] + arr[pos] % mod) % mod
		temp[1] = pos
		sums[pos] = temp
	sums = sorted(sums)
	minimum = -1
	for pos in range(0, size - 1):
		if sums[pos][1] > sums[pos + 1][1] and (sums[pos + 1][0] - sums[pos][0] < minimum or minimum == -1):
			minimum = sums[pos + 1][0] - sums[pos][0]
	if sums[size - 1][0] > mod - minimum:
		minimum = mod - sums[size - 1][0]
	print(mod - minimum)


import sys
n = int(input().strip())
for _ in range(n):
	(size, mod) = [int(val) for val in input().strip().split(' ')]
	arr = [int(val) for val in input().strip().split(' ')]
	sums = [-1] * size
	temp = [-1] * 2
	temp[0] = arr[0] % mod
	temp[1] = 0
	sums[0] = temp
	for pos in range(1, size):
		temp = [-1] * 2
		temp[0] = (sums[pos - 1][0] + arr[pos] % mod) % mod
		temp[1] = pos
		sums[pos] = temp
	sums = sorted(sums)
	minimum = -1
	for pos in range(0, size - 1):
		if sums[pos][1] > sums[pos + 1][1] and (sums[pos + 1][0] - sums[pos][0] < minimum or minimum == -1):
			minimum = sums[pos + 1][0] - sums[pos][0]
	if sums[size - 1][0] > mod - minimum:
		minimum = mod - sums[size - 1][0]
	print(mod - minimum)


from collections import defaultdict
for _ in range(int(input().strip())):
	(n, m) = map(int, input().strip().split())
	cumsum = defaultdict(list)
	curr = 0
	ar = tuple(map(lambda x: int(x) % m, input().strip().split()))
	for i in range(n):
		curr = (curr + ar[i]) % m
		cumsum[curr].append(i)
	sortsum = sorted(cumsum)
	result = sortsum[-1]
	for i in range(len(sortsum) - 1):
		if cumsum[sortsum[i]][-1] > cumsum[sortsum[i + 1]][0]:
			result = max(result, m + sortsum[i] - sortsum[i + 1])
	print(result)


import sys
n = int(input().strip())
for _ in range(n):
	(size, mod) = [int(val) for val in input().strip().split(' ')]
	arr = [int(val) for val in input().strip().split(' ')]
	sums = [-1] * size
	temp = [-1] * 2
	temp[0] = arr[0] % mod
	temp[1] = 0
	sums[0] = temp
	for pos in range(1, size):
		temp = [-1] * 2
		temp[0] = (sums[pos - 1][0] + arr[pos] % mod) % mod
		temp[1] = pos
		sums[pos] = temp
	sums = sorted(sums)
	minimum = -1
	for pos in range(0, size - 1):
		if sums[pos][1] > sums[pos + 1][1] and (sums[pos + 1][0] - sums[pos][0] < minimum or minimum == -1):
			minimum = sums[pos + 1][0] - sums[pos][0]
	if sums[size - 1][0] > mod - minimum:
		minimum = mod - sums[size - 1][0]
	print(mod - minimum)


import sys
n = int(input().strip())
for _ in range(n):
	(size, mod) = [int(val) for val in input().strip().split(' ')]
	arr = [int(val) for val in input().strip().split(' ')]
	sums = [-1] * size
	temp = [-1] * 2
	temp[0] = arr[0] % mod
	temp[1] = 0
	sums[0] = temp
	for pos in range(1, size):
		temp = [-1] * 2
		temp[0] = (sums[pos - 1][0] + arr[pos] % mod) % mod
		temp[1] = pos
		sums[pos] = temp
	sums = sorted(sums)
	minimum = -1
	for pos in range(0, size - 1):
		if sums[pos][1] > sums[pos + 1][1] and (sums[pos + 1][0] - sums[pos][0] < minimum or minimum == -1):
			minimum = sums[pos + 1][0] - sums[pos][0]
	if sums[size - 1][0] > mod - minimum:
		minimum = mod - sums[size - 1][0]
	print(mod - minimum)


n = int(input().strip())
for _ in range(n):
	(size, mod) = [int(val) for val in input().strip().split(' ')]
	arr = [int(val) for val in input().strip().split(' ')]
	sums = [-1] * size
	temp = [-1] * 2
	temp[0] = arr[0] % mod
	temp[1] = 0
	sums[0] = temp
	for pos in range(1, size):
		temp = [-1] * 2
		temp[0] = (sums[pos - 1][0] + arr[pos] % mod) % mod
		temp[1] = pos
		sums[pos] = temp
	sums = sorted(sums)
	minimum = -1
	for pos in range(0, size - 1):
		if sums[pos][1] > sums[pos + 1][1] and (sums[pos + 1][0] - sums[pos][0] < minimum or minimum == -1):
			minimum = sums[pos + 1][0] - sums[pos][0]
	if sums[size - 1][0] > mod - minimum:
		minimum = mod - sums[size - 1][0]
	print(mod - minimum)


from itertools import accumulate
for q in range(int(input().strip())):
	(n, m) = (int(s) for s in input().strip().split(' '))
	I = [int(s) for s in input().strip().split(' ')]
	A = [(x % m, i) for (i, x) in enumerate(accumulate(I))]
	A.sort()
	out = A[-1][0]
	for i in range(n - 1):
		j = 1
		while i + j < n and m + A[i][0] - A[i + j][0] > out:
			if A[i][1] < A[i + j][1]:
				j += 1
			else:
				out = m + A[i][0] - A[i + j][0]
				break
	print(out)


import sys
n = int(input().strip())
for _ in range(n):
	(size, mod) = [int(val) for val in input().strip().split(' ')]
	arr = [int(val) for val in input().strip().split(' ')]
	sums = [-1] * size
	temp = [-1] * 2
	temp[0] = arr[0] % mod
	temp[1] = 0
	sums[0] = temp
	for pos in range(1, size):
		temp = [-1] * 2
		temp[0] = (sums[pos - 1][0] + arr[pos] % mod) % mod
		temp[1] = pos
		sums[pos] = temp
	sums = sorted(sums)
	minimum = -1
	for pos in range(0, size - 1):
		if sums[pos][1] > sums[pos + 1][1] and (sums[pos + 1][0] - sums[pos][0] < minimum or minimum == -1):
			minimum = sums[pos + 1][0] - sums[pos][0]
	if sums[size - 1][0] > mod - minimum:
		minimum = mod - sums[size - 1][0]
	print(mod - minimum)


import sys
n = int(input().strip())
for _ in range(n):
	(size, mod) = [int(val) for val in input().strip().split(' ')]
	arr = [int(val) for val in input().strip().split(' ')]
	sums = [-1] * size
	temp = [-1] * 2
	temp[0] = arr[0] % mod
	temp[1] = 0
	sums[0] = temp
	for pos in range(1, size):
		temp = [-1] * 2
		temp[0] = (sums[pos - 1][0] + arr[pos] % mod) % mod
		temp[1] = pos
		sums[pos] = temp
	sums = sorted(sums)
	minimum = -1
	for pos in range(0, size - 1):
		if sums[pos][1] > sums[pos + 1][1] and (sums[pos + 1][0] - sums[pos][0] < minimum or minimum == -1):
			minimum = sums[pos + 1][0] - sums[pos][0]
	if sums[size - 1][0] > mod - minimum:
		minimum = mod - sums[size - 1][0]
	print(mod - minimum)


import sys
q = int(input())
for _ in range(q):
	(n, m) = [int(x) for x in input().split()]
	a_arr = [int(x) % m for x in input().split()]
	for i in range(1, len(a_arr)):
		a_arr[i] = (a_arr[i - 1] + a_arr[i]) % m
	a_arr = sorted([(x, i) for (i, x) in enumerate(a_arr)], key=lambda x: x[0])
	max_sum = a_arr[0][0]
	for i in range(0, len(a_arr) - 1):
		if a_arr[i][1] > a_arr[i + 1][1] and a_arr[i][0] < a_arr[i + 1][0]:
			max_sum = max(max_sum, (a_arr[i][0] - a_arr[i + 1][0]) % m)
	print(max(max_sum, a_arr[-1][0]))