Hearing that the princess is imprisoned in a castle, Hero Peng is determined: regardless of the hardships on the road, the strength of the guards, whether the princess will be captured again after being rescued, whether she is beautiful, or whether she will fall in love with him, he will march toward the castle without hesitation.

However, some situations have arisen on the road to the castle. Abstractly, imagine the map is in the first quadrant of a 2D plane. At each horizontal position $x$, there is a support point with height $h_x$. If Hero Peng does not land on a support point, he will fall and fail his journey. Initially, Hero Peng is at the starting point $(1, h_1)$, and the castle entrance is at $(n, h_n)$. Hero Peng can jump from support point $(x, h_x)$ to support point $(x+1, h_{x+1})$. However, Hero Peng's jump energy is limited to $d$, meaning each jump must satisfy the condition $|h_{x+1} - h_x| \le d$. In other words, if the vertical difference between two adjacent support points is greater than $d$, Hero Peng cannot make the jump!

Fortunately, Hero Peng has a trump card. At the starting point, he can spend one gold coin to increase or decrease the height of any support point by $1$ unit. However, the heights of the starting point and the castle entrance cannot be changed, and once he leaves the starting point, he can no longer use this trump card.

Hero Peng was told that $100$ gold coins can be exchanged for $1$ unit of health. Therefore, he hopes to spend as few gold coins as possible to save more health. He has finally found you, an enthusiastic expert, to help him plan his route so that he spends the minimum number of gold coins to reach the castle.

Input

The first line contains an integer $m$ ($m \le 5$), representing the number of times the problem needs to be solved. The next $2m$ lines represent the input data blocks for each query. Each input data block occupies $2$ lines: the first line contains two integers $n$ and $d$, representing the number of support points that must be passed from the start to the castle entrance and the maximum allowed vertical difference for each jump, separated by a space. The input guarantees $2 \le n \le 5000$ and $0 \le d \le 10^9$. The second line contains $n$ non-negative integers $h_1, h_2, \ldots, h_n$ separated by spaces, where $h_i$ ($1 \le i \le n$) represents the height of the $i$-th support point. Specifically, $h_1$ is the height of the support point where Hero Peng starts, and $h_n$ is the height of the support point at the castle entrance. The input guarantees $0 \le h_i \le 10^9$ for all $1 \le i \le n$.

Output

The output contains $m$ lines, where the $i$-th line ($1 \le i \le m$) represents the minimum number of gold coins Hero Peng must spend to reach the castle for the $i$-th query. If it is impossible to reach the castle regardless of how the trump card is used, output impossible. The input guarantees that the answer fits within an int64 range.

Examples

Input 1

3
10 2
4 5 10 6 6 9 4 7 9 8
3 1
6 4 0
4 2
3 0 6 3

Output 1

6
impossible
4

Note

For the first input data block, $d=2$. By decreasing the third support point by $3$ units, decreasing the sixth support point by $1$ unit, and increasing the seventh support point by $2$ units, the original sequence becomes: $4\ 5\ 7\ 6\ 6\ 8\ 6\ 7\ 9\ 8$. At this point, the vertical difference between any adjacent support points does not exceed $2$, and Hero Peng can reach the castle.

For the second input data block, $d=1$. Regardless of how the height of the second support point is adjusted, it is impossible to make the vertical difference between any adjacent support points not exceed $1$.

For the third input data block, $d=2$. By increasing the second support point by $1$ unit and decreasing the third support point by $3$ units, the condition is satisfied.

Subtasks

20%: $n \le 100$

40%: $n \le 1000$

100%: $n \le 5000$