题目描述

给定一个长度为 $n$ 的数列 $a_i(1\le i\le n)$，需要生成一个数列 $b_i(1\le i\le n)$，每个位置的得分为 $abs(b_i-a_i)$，总得分为各个位置得分的总和，要求 $abs(b_i-b_{i+1})\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$，$1\le d\le 10^9$，$1\le a_i\le 10^9$。