Kim Kangsan

Kim Kangsan is an artificial mountain built by stacking bricks, where people come to practice rock climbing. Its slope is so steep, however, that beginners struggle to climb it. The caretaker, Sanggeun, wants to reshape it to be gentler.

Kim Kangsan consists of $n$ brick piles in a row; the $i$-th pile from the left has $h_i$ bricks stacked on it. The height difference between two adjacent piles is $|h_{i+1} - h_i|$. Sanggeun wants every adjacent pair of piles to have a height difference of at most $d$.

Sanggeun may add bricks to or remove bricks from any pile, but he cannot change the number of bricks in the first pile or the last pile. Adding or removing a single brick costs $1$ unit of effort, and Sanggeun wants to minimize the total effort.

Given the height of every pile, find the minimum number of bricks that must be added or removed so that every adjacent height difference is at most $d$. If it is impossible to satisfy the condition, print impossible.

The first line contains the number of test cases $T$. ($1 \le T \le 100$)

Each test case consists of two lines. The first line contains the number of piles $n$ and the maximum allowed height difference $d$, separated by a space. ($2 \le n \le 100$, $0 \le d \le 10^9$) The second line contains the number of bricks on each pile, $h_1, h_2, \dots, h_n$, separated by spaces. ($0 \le h_i \le 10^9$)

For each test case, print on its own line the minimum number of bricks that must be added or removed so that every adjacent height difference is at most $d$. If the condition cannot be satisfied, print impossible.