# https://www.hackerrank.com/challenges/maximise-sum

# Accept input
##

def respond_bad_input
    puts "Bad input."
end

def check_for_new_max(mod, array, old_max)
    (get_mod_sum(mod,array)) > old_max
end

def get_mod_sum(mod, array)
    (array.inject{ |sum,x| sum + x }) % mod
end

index_size = 0
index_modulo = 1
index_array = 2

test_cases_count = 0
test_cases = []

input_array = ARGF.to_a

if input_array.count > 0
    test_cases_count = input_array[0]
else
    respond_bad_input
end

(1..(input_array.count-1)).step(2).each do |index|
    if input_array.count-1 > index+1
        respond_bad_input
    else
        size = input_array[index].split(" ")[0].to_i
        modulo = input_array[index].split(" ")[1].to_i
        test_array = input_array[index+1].split(" ")
        test_array.map!{ |value| value.to_i }

        test_cases.push([size, modulo, test_array ])
    end
end

# Run each test case
##
test_cases.each do |current_case|
    max_value = 0

    current_case[index_array].each_with_index do |value, index|

        sub_array = [value]

        if check_for_new_max(current_case[index_modulo], sub_array, max_value)
            max_value = get_mod_sum(current_case[index_modulo], sub_array)
        end

        (index..(current_case[index_array].count-1)).each do |sub_index|
            sub_array = sub_array.push sub_index

            if check_for_new_max(current_case[index_modulo], sub_array, max_value)
                max_value = get_mod_sum(current_case[index_modulo], sub_array)
                max_array = sub_array
            end
        end
    end

    puts max_value
end