You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

背景

小司特有的哼(zéng~)

题目描述

由崎星空和由崎司正在超市购物，发现超市有一个活动， 将给你一个长度为n的数组$a$,($a_1$,$a_2$.......$a_n$)，当$a_i$<=$a_i$$_-$$_1$ ($2<=i<=n$)时，你可以进行以下两个操作：

1. 消耗1枚硬币：将$a_i$移动到$a_j$，使A=$a_i$，如下：

如果i>j， j～i-1这个区间的数往右移1位.($a_i=$$a_{i-1}$，$a{_i-1}=$$a_{i-2}$.....$a_{j+1}=$$a_j$)，$a_j$=A。

如果i<j， i+1～j这个区间的数往左移1位.（$a_i$=$a_{i+1}$，$a_{i+1}$=$a_{i+2}$.....$a_{j-1}$=$a_j$），$a_j$=A。

2. 消耗2枚硬币,将$a_i$从数组中删除，每进行一次该操作，数组的长度就会-1，既n会-1，如下：

(i+1)～n这个区间的数往左移1位. ($a_i$=$a_{i+1}$，$a_{i+1}$=$a_{i+2}$......$a_{n-1}$=$a_{n}$，最后将$a_n$删除)。

例如有$n$=5,$a$={2,1,3,4,5}。我们可以对$a_2$进行操作，选择操作1，（选择$j$=1，那么$a$={1,2,3,4,5}，选择$j$=4，那么$a$={2,3,4,1,5}），选择操作2，那么$a$={2,3,4,5}。

问你能不能在硬币用完前，使得数组内的数严格递增，并且商家保证数组内相同的数一定连续。 由于完成上面的任务后，所剩余的硬币可以在奖品区挑选任意的奖励，所以由崎司希望以最少的硬币完成这个任务，并且她还想知道剩多少硬币。

输入

第一行输入一个t，表示有t轮，(1<=t<=10)

每轮的第一行输入两个整数n,m，表示数组的长度和拥有的硬币（1<=n<=$10^6$，0<=m<=10$^{6}$)

每轮的第二行输入n个整数，$a_1$，$a_2$.....$a_n$，(0<=$a_i$<=$10^{6}$）。

输出

每轮有一个输出，如果可以完成任务，输出最多能剩多少枚硬币，如果不能完成任务，输出"heng"。

样例

样例1

2
5 5
2 1 3 4 5
5 1
1 2 2 3 4

4
heng