변형 LCS

LCS는 최장 공통 부분 수열(longest common subsequence)을 뜻하고, 잘 알려진 문제다. 이 문제에서 수열은 정수를 나열한 목록이다. 수열 $Y$에서 원소 0개 이상을 지우고 남은 원소의 순서를 그대로 두었을 때 수열 $X$가 나오면 $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$). 이어지는 $T$개의 줄에 테스트 케이스가 한 줄씩 주어진다. 각 줄에는 공백 하나로 구분된 정수 여섯 개 $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$). 차례대로 첫 번째 수열의 길이, 첫 번째 수열의 첫 원소, 첫 번째 수열의 증가량, 두 번째 수열의 길이, 두 번째 수열의 첫 원소, 두 번째 수열의 증가량이다.

테스트 케이스마다 두 수열의 최장 공통 부분 수열의 길이를 정수 하나로 한 줄에 출력한다.