Boy Vasya loves to travel very much. In particular, flying in airplanes brings him extraordinary pleasure. He was about to fly to another city, but the runway was heavily covered with snow and needed to be cleared. The runway can be represented as (n) consecutive sections numbered from (1) to (n). The snowstorm was quite strong, but it has already stopped, so Vasya managed to calculate that the (i)-th section is covered with (a_i) meters of snow. For such situations, the airport has a snowplow that works in a rather unusual way. In one minute, the snowplow can do the following: Choose a consecutive segment of length no more than (d) and remove one meter of snow from the most snow-covered sections. Formally, one can choose (1 \le l \le r \le n) ((r - l + 1 \le d)). After that, (c = \max \{ a_l, a_{l + 1}, \ldots , a_r \}) is calculated, and if (c > 0), then for all (i \colon l \le i \le r) such that (a_i = c), the value of (a_i) is decreased by one. Formally, one can choose (1 \le l \le r \le n) ((r - l + 1 \le d)). After that, (c = \max \{ a_l, a_{l + 1}, \ldots , a_r \}) is calculated, and if (c > 0), then for all (i \colon l \le i \le r) such that (a_i = c), the value of (a_i) is decreased by one. Vasya has been preparing for the flight for a long time and wants to understand how much time he has left to wait until all sections are completely cleared of snow. In other words, it is required to calculate the minimum number of minutes that the snowplow will need to achieve (a_i = 0) for all (i) from (1) to (n). Each test contains multiple test cases. The first line contains the number of test cases (t) ((1 \le t \le 2 \cdot 10^5)). The description of the test cases follows. The first line of each test case contains two integers (n) and (d) ((1 \le n \le 5 \cdot 10^5, 1 \le d \le n)) — the number of sections on the runway and the maximum length