#P9611. Training

    ID: 6223 传统题 3000ms 1024MiB 尝试: 2 已通过: 2 难度: 8 上传者: 标签>CF2400提高+/省选-向下取整与向上取整一维前缀和等差数列求和

Training

题目描述

本题来自 ARC 123 Training。

小 X 和小 Y 在训练,初始时小 X 的等级为 AXA_X,小 Y 的等级为 AYA_Y,他们每天都会学习知识。

两个人的学习能力是不一样的,小 X 过了 BXB_X 天会升一级,换句话说,小 X 会在第 k×BXk\times B_X 天时升到 AX+kA_X+k 级,小 Y 与之类似。

试求出在第 11 天到第 NN 天中,小 X 的等级等于小 Y 的等级的天数。

输入格式

本题有多组数据。

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

每组数据仅一行五个整数,表示 N,AX,BX,AY,BYN,A_X,B_X,A_Y,B_Y。

输出格式

对于每组数据,输出仅一行一个整数,表示你的答案。

样例

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

我们将解释第一个样例。

对于前 1010 天,每个人的等级有:

  • 小 X 的等级:5,5,6,6,6,7,7,7,8,85,5,6,6,6,7,7,7,8,8;
  • 小 Y 的等级:4,5,5,6,6,7,7,8,8,94,5,5,6,6,7,7,8,8,9。

容易发现有 66 天两人等级相同。

数据范围

对于所有数据,满足 1≤T≤2×1051\le T\le 2\times 10^5,1≤N≤1091\le N\le 10^9,1≤AX,AY,BX,BY≤1061\le A_X,A_Y,B_X,B_Y\le 10^6。