#P19006. 【CodeChef START263A】Alarm Alert

【CodeChef START263A】Alarm Alert

题目描述

两个闹钟分别以 XX 秒和 YY 秒为周期。从时刻 00 开始计时,第一个闹钟在 X,2X,3X,…X,2X,3X,\ldots 时响,第二个在 Y,2Y,3Y,…Y,2Y,3Y,\ldots 时响。

两个不同的闹钟各响一次,若这两次响铃的时间差不超过 DD 秒,你就会在其中较晚的那次响铃时醒来。两个闹钟同时响也满足条件。求满足条件的最早时刻,保证这个时刻存在。

输入格式

第一行是整数 TT,表示测试组数。

接下来每行一组数据,包含三个整数 X,Y,DX,Y,D。

输出格式

每组数据输出一行,包含一个整数,表示最早醒来的时刻。

数据范围

  • 1≤T≤1051 \le T \le 10^5。
  • 1≤X,Y≤1061 \le X,Y \le 10^6。
  • 0≤D<min⁡(X,Y)0 \le D < \min(X,Y)。
  • 所有测试组的 XX 之和不超过 10610^6,YY 之和也不超过 10610^6。

样例

5
3 5 0
2 3 1
6 8 2
9 9 0
987799 975780 200
15
3
8
9
4731557220

CodeChef 原题:Alarm Alert