LCS 代表最长公共子序列（Longest Common Subsequence），这是一个众所周知的问题。在本题中，序列是指一个整数列表。如果序列 $X$ 可以通过从序列 $Y$ 中删除零个或多个元素且不改变剩余元素顺序而得到，则称序列 $X$ 是序列 $Y$ 的子序列。

在本题中，你将得到两个序列，你的任务是找出既是第一个序列的子序列，又是第二个序列的子序列的最长序列的长度。

题目并未直接给出序列本身。对于每个序列，你将得到三个整数 $N$、$F$ 和 $D$，其中 $N$ 是序列的长度，$F$ 是序列的第一个元素。除第一个元素外，每个元素都比它前面的元素大 $D$。

例如，$N = 5$，$F = 3$，$D = 4$ 代表以下序列：$[3, 7, 11, 15, 19]$。

题目保证至少存在一个同时属于两个序列且不大于 $1,000,000$ 的整数。

输入格式

你的程序将在一个或多个测试用例上进行测试。输入的第一行是一个整数 $T$，表示测试用例的数量（$1 \le T \le 100$）。接下来的每一行描述一个测试用例，包含 6 个由空格分隔的整数 $N_1, F_1, D_1, N_2, F_2, D_2$（$1 \le N_1, N_2 \le 10^{18}$ 且 $1 \le F_1, D_1, F_2, D_2 \le 10^9$），分别代表第一个序列的长度、第一个序列的第一个元素、第一个序列的增量值、第二个序列的长度、第二个序列的第一个元素以及第二个序列的增量值。

输出格式

对于每个测试用例，输出一行，包含一个整数，表示给定两个序列之间的最长公共子序列的长度。

样例

样例输入 1

3
5 3 4 15 3 1
10 2 2 7 3 3
100 1 1 100 1 2

样例输出 1

4
3
50