Card Game (Large)

Bob likes card games. At his birthday party his friend Alice gave him a set of cards.

There are $N$ cards and each card has one integer written on it. Bob lays the cards on a desk from left to right and wants to discard some of them. Before discarding anything he fixes an integer $K$. Each discard takes three cards that are neighbours at that moment, and if the numbers on those three cards are $a$, $b$ and $c$ from left to right, they must satisfy

$c - b = b - a = K$

A discarded card leaves no gap, so the cards that were on either side of it become neighbours.

When several triples can be discarded, Bob picks the ones that leave the fewest cards at the end. Find that smallest number of remaining cards.

The first line contains the number of test cases $T$. $T$ test cases follow.

Each test case is two lines. The first line contains the number of cards $N$ and the number $K$ that Bob fixed, separated by a space. The second line contains the numbers written on the cards from left to right, $a_1, a_2, \dots, a_N$.

Limits

• $1 \le T \le 100$
• $1 \le N \le 100$
• $0 \le K \le 10^6$
• $1 \le a_i \le 10^6$ ($1 \le i \le N$)

For each test case print one line in the form Case #x: y, where $x$ is the test case number starting from 1 and $y$ is the smallest number of cards Bob can be left with after discarding.