You are given an array of $n$ positive integers $a_1, a_2, \ldots, a_n$ and a positive integer $k$.

In one operation, you may add either $0$ or $k$ to each $a_i$, i.e., choose another array of $n$ integers $b_1, b_2, \ldots, b_n$ where each $b_i$ is either $0$ or $k$, and update $a_i$ to $a_i + b_i$ for $1 \le i \le n$. Note that you can choose different values for each element of the array $b$.

Your task is to perform at most $k$ such operations to make $\gcd(a_1, a_2, \ldots, a_n) \gt 1$ $^{\text{∗}}$. It can be proved that this is always possible.

Output the final array after the operations. You do not have to output the operations themselves.

$^{\text{∗}}$$\gcd(a_1, a_2, \ldots, a_n)$ denotes the greatest common divisor (GCD) of $a_1, a_2, \ldots, a_n$.

Input

Each test contains multiple test cases. The first line contains the number of test cases $t$ ($1 \le t \le 1000$). The description of the test cases follows.

The first line of each test case contains two integers $n$ and $k$ ($1 \le n \le 10^5$, $1 \leq k \leq 10^9$) — the length of the array $a$ and the given constant.

The second line of each test case contains $n$ integers $a_1,a_2,\ldots,a_n$ ($1 \le a_i \le 10^9$) — the elements of the array $a$.

It is guaranteed that the sum of $n$ over all test cases does not exceed $10^5$.

Output

For each test case, output an array of $n$ integers in a new line — the final array after the operations. The integers in the output should be within the range from $1$ to $10^9 + k^2$.

If there are multiple valid outputs, you can output any of them.

Note that you do not have to minimize the number of operations.

Note

In the first test case, the output $[8,10,10]$ is valid because $\gcd(8, 10, 10) = 2 \gt 1$, and the array $[2, 7, 1]$ can be transformed into $[8, 10, 10]$ using at most $3$ operations. One possible sequence of operations is shown below:

Operation$b$Resulting $a$$1$$[3,0,3]$$[5,7,4]$$2$$[0,0,3]$$[5,7,7]$$3$$[3,3,3]$$[8,10,10]$

Other outputs like $[2, 10, 4]$, $[8, 16, 4]$, and $[5, 10, 10]$ are also considered valid.

In the second test case, the output $[7, 14, 21, 14]$ is valid because:

• $\gcd(7, 14, 21, 14) = 7 \gt 1$.
• Starting from $[2, 9, 16, 14]$, applying the operation with $b = [5, 5, 5, 0]$ yields $[7, 14, 21, 14]$, requiring no more than $5$ operations.