Modified LCS

Time limit1sMemory limit128 MB

Summary

Count the terms shared by two strictly increasing arithmetic progressions, which equals their longest common subsequence.

Level: Medium5 of 10
Topics: Number theory, Math
Solved: No attempts yet

Problem

LCS stands for longest common subsequence, a well known problem. A sequence in this problem is a list of integers, and a sequence $X$ is a subsequence of a sequence $Y$ when you can obtain $X$ by deleting zero or more elements from $Y$ and leaving the remaining elements in their original order.

You are given two sequences. Find the length of the longest sequence that is a subsequence of both of them.

The sequences themselves are not given. Each sequence is described by three integers $N$ , $F$ and $D$ , where $N$ is the length of the sequence and $F$ is its first element. Every element except the first is greater than the element before it by $D$ .

For example, $N = 5$ , $F = 3$ and $D = 4$ describes the sequence $[3, 7, 11, 15, 19]$ .

At least one integer belongs to both sequences and is not greater than 1,000,000.

Input

The first line contains a single integer $T$ , the number of test cases ( $1 \le T \le 100$ ). Each of the next $T$ lines describes one test case and contains six integers separated by a single space, $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$ ). They are the length of the first sequence, the first element of the first sequence, the increment of the first sequence, the length of the second sequence, the first element of the second sequence, and the increment of the second sequence, in that order.

Output

For each test case, print one line with a single integer, the length of the longest common subsequence of the two sequences.

Examples1

Example 1

Input

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

Expected output

4
3
50