Super Greedy
Two players are engaged in a game called "Greedy." There are n piles, each containing a_i candies. The players take turns, and on each turn, they can remove any number of candies from 1 to k from any single pile. The player who removes the last candy from any pile loses the game. Determine how many different ways the first player can make their initial move to ensure a win, assuming both players play optimally.
Input
The first line contains the number of games t (1 ≤ t ≤ 10^5). Each of the next t lines describes a game with three values: n (1 ≤ n ≤ 10^5), k (1 ≤ k ≤ 10^9), followed by n integers a_i (1 ≤ a_i ≤ 10^9) representing the number of candies in each pile.
It is guaranteed that the total number of piles across all games does not exceed 10^5.
Output
For each game, output the number of ways the first player can make their first move to guarantee a win, assuming both players play optimally. If the first player cannot win, output 0.