题目描述

Maddy 和 Baddy 决定通过智慧的方法一较高下！
Maddy 和 Baddy 初始有一个含有 $n$ 个正整数的多重集合 $S = \{a_1, a_1 + d, a_1 + 2d, \dots, a_1 + (n-1)d\}$，她们决定玩一个游戏，游戏规则如下：

• 由 Maddy 开始操作，Maddy 和 Baddy 轮流操作。
• 每位玩家操作时需要 $S$ 中加入一个正整数。
• 当每位玩家都操作了 $m$ 次后，游戏结束。
• Maddy 的目标是让最终 $S$ 的 $k$-连通数尽可能大，Baddy 的目标是让最终 $S$ 的 $k$-连通数尽可能小。

其中的 $k$-连通数定义如下：

• 先将 $S$ 排序，对于每组相邻的数，若其差大于 $k$，则将连通数增加 1，连通数初始为 1。
• 一个等价的定义是在图上把 $S$ 上的元素作为顶点，差不大于 $k$ 的顶点之间连边，$k$-连通数即为连通块的数量。

假设 Maddy 和 Baddy 都是无比智慧的，在进行游戏时总会选择最优的策略，请帮助她们求出游戏结束时 $k$-连通数的值。

输入格式

第一行输入一个整数 $T$ ($1 \le T \le 100$)，表示数据组数。
每组测试数据输入的唯一一行输入 5 个整数 $n, a_1, d, m$ 和 $k$ ($1 \le n, a_1, m \le 100$，$0 \le d, k \le 100$)，分别表示初始 $S$ 的大小，等差数列的首项和公差，游戏的轮数，参量 $k$ 的值。

输出格式

每组测试数据输出一行一个整数 $ans$，表示在 Maddy 和 Baddy 选择最优的策略的情况下，游戏结束时 $S$ 的 $k$-连通数的值。

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

提示

样例 1 解释

对于第 1 个样例，初始的 $S = \{(2 + 0 \times 3), (2 + 1 \times 3), (2 + 2 \times 3)\} = \{2, 5, 8\}$，下给出一个可能的双方策略：

• Maddy 加入一个 13，$S = \{2, 5, 8, 13\}$；
• Baddy 加入一个 3，$S = \{2, 3, 5, 8, 13\}$；
• Maddy 加入一个 18，$S = \{2, 3, 5, 8, 13, 18\}$；
• Baddy 加入一个 7，$S = \{2, 3, 5, 7, 8, 13, 18\}$。

排序后相邻差依次为 $D_1 = 1$，$D_2 = 2$，$D_3 = 2$，$D_4 = 1$，$D_5 = 5$，$D_6 = 5$，比 $k = 2$ 大的共有 2 个，$k$-连通数为 3。