## 22544: Modified LCS

[提交][状态][讨论版][命题人:]

## 题目描述

LCS stands for longest common subsequence, and it is a well known problem. A sequence in this problem
means a list of integers, and a sequence X is considered a subsequence of another sequence Y, when the
sequence X can be obtained by deleting zero or more elements from the sequence Y without changing the
order of the remaining elements.
In this problem you are given two sequences and your task is to nd the length of the longest sequence
which is a subsequence of both the given sequences.
You are not given the sequences themselves. For each sequence you are given three integersN, FandD,
whereNis the length of the sequence, Fis the rst element in the sequence. Each element except the
rst element is greater than the element before it byD.
For exampleN= 5,F= 3 andD= 4 represents the following sequence: [3, 7, 11, 15, 19].
There will be at least one integer which belongs to both sequences and it is not greater than 1,000,000.

## 输入

Your program will be tested on one or more test cases. The rst line of the input will be a single integer
T, the number of test cases (1 <=T<=100). Followed by the test cases, each test case is described in

one line which contains 6 integers separated by a single spaceN1 F1 D1 N2 F2 D2(1<=N1,N2<=10^18

and (1<= F1,D1,F2,D2<=10^9) representing the length of the rst sequence, the rst element in

the rst sequence, the incremental value of the rst sequence, the length of the second sequence, the rst
element in the second sequence and the incremental value of the second sequence, respectively.

## 输出

For each test case, print a single line which contains a single integer representing the length of the longest
common subsequence between the given two sequences.

## 样例输入

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


## 样例输出

4
3
50


[提交][状态]