You have a sack of n potatoes and a strip of land (n + 1) ⋅ k centimeters long.

You want to evenly plant the potatoes on this strip. If we mark the beginning of the strip as centimeter 0, then you want to plant the first potato at centimeter k, plant the second potato at centimeter 2k, ..., plant the n-th potato at centimeter nk (and then the strip of land ends at (n + 1) ⋅ k centimeters).

Each potato has a growth range r_i. This means that if you plant the potato at centimeter x, and it has enough space, it will grow you some new tasty potatoes all across [x − r_i, x + r_i].

However, a potato will never grow over another potato's growth territory, or beyond your strip of land - in other words, if the potato comes across the edge of the plot or bumps into a different potato plant, it stops growing in that direction.

Given n, k and r_i of your n potatoes, how many potatoes can you grow if you plant them optimally?

Input

The first line contains an integer 1 ≤ T ≤ 20 - the number of test cases. T test cases follow.

For each test case:

The first line contains the integers 1 ≤ n ≤ 10⁶ and 1 ≤ k ≤ 10⁹. The second line contains n integers 1 ≤ r_i ≤ k - the growth radii of the potatoes.

The sum of n within an input file will never exceed 2 ⋅ 10⁶.

Output

For each test case, output a single integer: the maximum length of strip you can cover in grown potatoes.

Examples

Input

3
3 20
6 12 4
3 20
12 12 12
3 5
1 1 5

Output

44
64
13

In the first case, if we plant the potatoes in the same order as in the input, that is 6->20cm, 12->40cm, 4->60cm, they will grow on [14,26], [28,52], [56,64] for a total of 12+24+8 = 44 cm of potatoes. Any other order works just as well, though.

In the second case we don't really have much to choose from.. The potatoes would want to grow out to [8,32], [28,52], [48,72], but they get in each other's way. So they will end up growing on [8,30], [30,50], [50,72] for a total of 64cm.

In the last case the best order to plant the potatoes is, for example, 5 1 1.