Sudama is coming back from his two-week vacation at the other continent (Dwarka). But when Sudama arrived at the airport, he realized that he had got no gifts for his K friends! He still had some time before his flight, so he went for a walk around the airport hoping to find something suitable.

Soon Sudama found a candy store and decided to buy some of his favorite candies for his friends. The store offers N packs of these candies, where pack i contains Ai candies.

Another reason Sudama decided to buy candies is that he is fond of collecting empty candy packs from various parts of the world. That's why he decided to buy exactly M packs and present the friends with the candies and keep the packs for his collection. Sudama would also like the total number of candies to be divisible by K so that an equal distribution of candies between friends is possible. Among all possible sets of packs, he would like to buy a set with the smallest possible total number of candies (money is the reason).

Your task is to help Sudama, of course.

Input

The first line of the input file contains an integer T -- the number of test cases (no more than 5). T test cases follow, and each test case consists of two lines. The first of them contains three integers N, M and K (1 ≤ M ≤ N ≤ 50000, 1 ≤ K ≤ 20). The second of them contains N integers Ai (1 ≤ Ai ≤ 10^9).

Output

For each test case, output just one line containing the smallest possible total number of bought candies, or -1 if it's impossible to buy exactly M packs so that the total number of candies is divisible by K.