题目描述

Aya 是修车专家，但是有很多彩黑批评她的修车技术还不如劈瓦大师 Amita， Aya 在网上自搜发现有非常多彩黑，她决定将彩黑统统屏蔽。

在接下来 \(n\) 分钟内，每分钟会出现 \(a_i\) 条新的彩黑评论， Aya 每分钟至多可以屏蔽 \(x\) 条之前未屏蔽过的彩黑评论，在此我们认为，每一分钟都是彩黑评论先出现，然后 Aya 开始屏蔽彩黑评论。

Aya 想知道， \(n\) 分钟后还剩余多少条彩黑评论没有被屏蔽。

输入格式

第一行输入一个正整数 \(T(1 \le T \le 2 \times 10^5)\)，表示数据组数。

对于每一组数据：

第一行输入两个正整数 \(n, x(1 \le n \le 10^5, 1 \le x \le 10^9)\)，表示分钟数，每分钟可以屏蔽的彩黑评论数量。

第二行输入 \(n\) 个正整数 \(a_i(1 \le a_i \le 10^9)\)，表示每分钟会出现的彩黑评论数量。

数据保证 \(\sum n \le 3 \times 10^5\)。

输出格式

对于每组数据输出一个整数表示答案。

样例输入

1
6 3
1 1 4 5 1 4

样例输出

2

提示

第1分钟出现1条彩黑评论，Aya 屏蔽1条彩黑评论，累计剩余0条彩黑评论。

第2分钟出现1条彩黑评论，Aya 屏蔽1条彩黑评论，累计剩余0条彩黑评论。

第3分钟出现4条彩黑评论，Aya 屏蔽3条彩黑评论，累计剩余1条彩黑评论。

第4分钟出现5条彩黑评论，Aya 屏蔽3条彩黑评论，累计剩余3条彩黑评论。

第5分钟出现1条彩黑评论，Aya 屏蔽3条彩黑评论，累计剩余1条彩黑评论。

第6分钟出现4条彩黑评论，Aya 屏蔽3条彩黑评论，累计剩余2条彩黑评论。

因此答案为2。