seuOJ386 - 种菜

题目描述

在 MC\text{MC} 11451.4 版本中加入了两种植物 X 和 Y。

在刚种下时，两种植物的高度分别为 AX,AYA_X,A_Y，每隔 BX,BYB_X,B_Y 天，两种植物会长高一格。

现在 Steve 同时种下了两棵植物，求在接下来的 nn 天 中，有多少天它们的高度相同。

输入格式

第一行一个正整数 TT 表示数据组数。

然后 TT 行，每行 55 个正整数 N,AX,BX,AY,BYN,A_X,B_X,A_Y,B_Y。

T≤2⋅105,1≤n≤109,1≤AX,AY,BX,BY≤106T\leq 2\cdot 10^{5},1\leq n\leq 10^9,1\leq A_X,A_Y,B_X,B_Y\leq 10^6。

输出格式

对于每组数据输出一行表示答案。

样例

样例输入

5
10 5 3 4 2
5 5 3 4 2
100 5 3 4 2
10 5 3 4 3
10 5 10 5 9

样例输出

6
3
6
0
9