Problem Description

Maddy and Baddy decide to compete in a battle of wits.
Initially, Maddy and Baddy have a multiset $S$ of $n$ positive integers: $S = \{a_1, a_1 + d, a_1 + 2d, \dots, a_1 + (n-1)d\}$. They decide to play a game with the following rules:

• Maddy moves first, and Maddy and Baddy take turns.
• On each move, the current player must add one positive integer into $S$.
• The game ends after each player has made $m$ moves.
• Maddy’s goal is to make the final $k$-connectivity number of $S$ as large as possible, while Baddy’s goal is to make it as small as possible.

The $k$-connectivity number is defined as follows:

• First sort $S$. For each pair of adjacent numbers, if their difference is greater than $k$, increase the connectivity number by 1. The connectivity number starts at 1.
• An equivalent definition is: build a graph where each element of $S$ is a vertex, and add an edge between two vertices if their difference is at most $k$. The $k$-connectivity number is the number of connected components.

Assume both Maddy and Baddy are perfectly smart and always choose the best strategy. Please compute the value of the $k$-connectivity number when the game ends.

Input Format

The first line contains an integer $T$ ($1 \le T \le 100$), the number of test cases.
For each test case, the only line contains five integers $n, a_1, d, m$ and $k$ ($1 \le n, a_1, m \le 100$, $0 \le d, k \le 100$), representing the initial size of $S$, the first term and common difference of the arithmetic progression, the number of rounds, and the parameter $k$, respectively.

Output Format

For each test case, output one integer $ans$ in one line, meaning the $k$-connectivity number of $S$ at the end of the game when both Maddy and Baddy play optimally.

4
3 2 3 2 2
4 3 2 5 1
4 1 1 5 2
9 7 8 3 0

3
6
6
12

Hint

Explanation for Sample 1

For the first sample, the initial $S = \{(2 + 0 \times 3), (2 + 1 \times 3), (2 + 2 \times 3)\} = \{2, 5, 8\}$. One possible sequence of moves is:

• Maddy adds 13, $S = \{2, 5, 8, 13\}$.
• Baddy adds 3, $S = \{2, 3, 5, 8, 13\}$.
• Maddy adds 18, $S = \{2, 3, 5, 8, 13, 18\}$.
• Baddy adds 7, $S = \{2, 3, 5, 7, 8, 13, 18\}$.

After sorting, the adjacent differences are $D_1 = 1$, $D_2 = 2$, $D_3 = 2$, $D_4 = 1$, $D_5 = 5$, $D_6 = 5$. There are 2 differences greater than $k = 2$, so the $k$-connectivity number is 3.

Translated by ChatGPT 5