Happy New Year 2010

Given a sequence of positive integers a₁, a₂, ..., a_N, and 1 ≤ i ≤ j ≤ N, the partial sum from
i to j is a_i + a_i+1 + ... + a_j.

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 a₁, a₂, ..., a_N, 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

Scoring

The shortest code (the less number of bytes) the better. The number of points displayed in the ranking is scaled so that it is equal to 10 for the contestant whose solution is the shortest, and proportionally less for all solutions with longer codes.