Description

给定n个数{a1，a2，...,an},你的任务是将他调整成另外一个数列{b1,b2,...,bn}（将a[i]变大或者变小成b[i])其中满足b1=a1,bn=an,|bi-bi+1|<=d (1<= i < n)(即相邻两项绝对值不大于d). 选择合适的数列b,使得sigma|ai-bi|的值最小

Input

首先一个整数cas,表示接下来由cas个数据 每组数据第一行两个整数n,d(2<=n<=100， d<=30) 第二行包含n个整数,表示数组a, 每个整数在[0,50000]之间

Output

如果能调整成功,输出sigma|ai-bi|的最小值， 否则输出impossible

Sample

Input

2
3 1
6 4 0
4 2
3 0 6 3

Output

impossible
4

Hint

第二组数据调整成 {3,3,5,3}