数列

给定一个长度为 $n$ 的数列 $a_i$（$1\le i\le n$），需要构造一个长度同样为 $n$ 的数列 $b_i$。

位置 $i$ 的得分为 $\lvert b_i-a_i\rvert$，总得分为所有位置得分之和。构造的数列需要满足：

• $\lvert b_i-b_{i+1}\rvert\le d$；
• $a_1=b_1$；
• $a_n=b_n$。

请在满足上述条件的前提下，使总得分最小。

输入格式

输入包含多组数据。

第一行包含一个整数 $t$，表示数据组数。

对于每组数据：

• 第一行包含两个整数 $n$ 和 $d$；
• 第二行包含 $n$ 个整数 $a_i$，表示给定的数列。

输出格式

对于每组数据，输出一行。

如果存在合法数列，则输出最小总得分；否则输出 impossible。

样例输入

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

样例输出

6
impossible
4

数据范围

• $1\le n\le 100$；
• $0\le d\le 10^9$；
• $0\le a_i\le 10^9$。

来源与许可

本题题面与测试数据整理自 BZOJ。

样例 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

输出

6
impossible
4