BaoBao 和 DreamGrid 正在玩一个关于奇怪按钮的游戏。这个按钮连接着一个 LED 灯（初始状态为关闭）、一个计数器和一个计时器，其功能如下：

• 当按下按钮时，计时器被设置为 $(v + 0.5)$ 秒（无论按下按钮前计时器的值是多少），其中 $v$ 是给定的整数，并开始倒计时；
• 当在 LED 灯关闭时按下按钮，LED 灯会亮起；
• 当在 LED 灯亮起时按下按钮，计数器的值会增加 1；
• 当计时器倒计时到 0 时，LED 灯熄灭。

在游戏过程中，BaoBao 和 DreamGrid 会定期按下按钮。如果当前真实时间（即游戏开始后经过的时间，而不是计时器的值）以秒为单位是一个整数，并且是给定整数 $a$ 的倍数，BaoBao 会立即按下按钮 $b$ 次；如果当前时间以秒为单位是一个整数，并且是另一个给定整数 $c$ 的倍数，DreamGrid 会立即按下按钮 $d$ 次。

注意： 0 是每个整数的倍数； BaoBao 和 DreamGrid 都非常擅长按下按钮，因此他们完成按键操作不需要时间； * 如果 BaoBao 和 DreamGrid 被安排在同一秒按下按钮，DreamGrid 将在 BaoBao 完成按下 $b$ 次按钮后，开始按下 $d$ 次按钮。

游戏从 0 秒开始，在 $t$ 秒后结束（如果按钮在 $t$ 秒时被按下，游戏将在按下按钮后结束）。请问游戏结束时计数器的值是多少？

输入格式

输入包含多个测试用例。第一行包含一个整数 $T$（约 100），表示测试用例的数量。对于每个测试用例：

第一行包含六个整数 $a, b, c, d, v$ 和 $t$ ($1 \le a, b, c, d \le 10^6, 1 \le v, t \le 10^{12}$)。其含义如上所述。

输出格式

对于每个测试用例，输出一行包含一个整数，表示游戏结束时计数器的值。

样例

样例输入 1

2
8 2 5 1 2 18
10 2 5 1 2 10

样例输出 1

6
4

说明

我们现在解释第一个样例测试用例。

• 在 0 秒时，LED 灯初始为关闭。BaoBao 按下按钮 2 次后，LED 灯亮起，计数器的值变为 1。计时器的值也被设置为 2.5 秒。随后 DreamGrid 按下按钮 1 次，计数器的值变为 2。
• 在 2.5 秒时，计时器倒计时到 0，LED 灯熄灭。
• 在 5 秒时，DreamGrid 按下按钮 1 次后，LED 灯亮起，计时器的值被设置为 2.5 秒。
• 在 7.5 秒时，计时器倒计时到 0，LED 灯熄灭。
• 在 8 秒时，BaoBao 按下按钮 2 次后，LED 灯亮起，计数器的值变为 3，计时器的值被设置为 2.5 秒。
• 在 10 秒时，DreamGrid 按下按钮 1 次后，计数器的值变为 4，计时器的值从 0.5 秒变为 2.5 秒。
• 在 12.5 秒时，计时器倒计时到 0，LED 灯熄灭。
• 在 15 秒时，DreamGrid 按下按钮 1 次后，LED 灯亮起，计时器的值被设置为 2.5 秒。
• 在 16 秒时，BaoBao 按下按钮 2 次后，计数器的值变为 6，计时器的值从 1.5 秒变为 2.5 秒。
• 在 18 秒时，游戏结束。