Description

Here is a Frieren picture to brighten your day!

There are N numbers, each number is positive and multiplier of K,
for e.g. if N = 10 and K = 3, the array should be [3, 6, 9, 12, 15, 18, 21, 24, 27, 30]

However, Mr. 景璞 change one of the number to -1, and then scrambled the order
for e.g. the array become [30, 21, 9, -1, 3, 24, 27, 15, 12, 18]

Your task is to find what number was changed
in the example above, the missing one will be 6

Note: To pass all test cases, you need to consider the Memory Limit and Time Limit
Hint: 10⁵ of long long will take around 0.8 MB of memory

Input

There are T testcases

Each testcase has integer N, followed by a_0, a₁, a₂, ..., a_N-1 in the next line, and then K

1 <= T <= 50

1 <= N <= 10⁵

1 <= K <= 10⁶

-1 <= a_i <= N * K

For the first 3 testcases, N <= 2000

Output

For each testcase, output the missing number, followed by '\n'

Sample Input  Download

Sample Output  Download

Tags

Discuss