PARTSUM - Partial Sums

no tags 

Given a sequence of positive integers a1, a2, ..., aN, and 1 ≤ ijN, the partial sum from
i to j is ai + ai+1 + ... + aj.

In this problem, you will be given such a sequence and two integers P and K. Your task is to find the smallest partial sum modulo P that is at least K.

For example, consider the following sequence of integers:

12     13     15     11     16     26     11

Here N = 7. Suppose K = 2 and P = 17. Then, the answer is 2 because 11 + 16 + 26 = 53 and 53 mod 17 is 2. On the other hand, if K = 0 the answer is 0 since 15 + 11 + 16 + 26 = 68 and 68 mod 17 is 0.

You may assume 1 ≤ N ≤ 100000.

Input

The first line of the input contains the number of test cases, T.

Each test case begins with a line containing three integers, N, K and P. This is followed by the values of a1, a2, ..., aN, one per line.

Output

Output one line per test case, containing the smallest partial sum modulo P that is at least K, as described above.

Example

Input:
1
7 2 17
12
13
15
11
16
26
11

Output:
2
Warning: large Input/Output data, be careful with certain languages

hide comments
:D: 2010-07-16 09:52:40

You can use 32 bit singed integers for all input data and intermediate calculations. Also you can assume that there always exists at least one sequence meeting the criteria (mod P at leask K)

Tony Beta Lambda: 2010-07-02 02:49:25

In fact P has an amusing upper bound. P <= 2 ^ 31...

.:: Pratik ::.: 2009-07-25 15:29:09

What are constraints? (P that is)

Last edit: 2009-07-25 15:30:22

Added by:Stephen Merriman
Date:2007-02-22
Time limit:1.510s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ERL JS-RHINO NODEJS PERL6 VB.NET
Resource:Indian Computing Olympiad, Online Programming Contest, July 06