题目描述

生日在二月二十九号的小可可常常嘀咕道：“今年为什么不是闰年呀！”

她对闰年的判断方式感到十分的不满，于是找到了你。

她规定了三个依次递增的正整数，$a, b, c$，且 $b$ 被 $a$ 整除，$c$ 被 $b$ 整除。

她认为，如果 $x$ 被 $a$ 整除但是不被 $b$ 整除，或者 $x$ 被 $c$ 整除，$x$ 即为闰年。换言之，$x$ 为闰年等效于在 C 语言中 $(x\%a==0 \&\& x\%b!=0) || x\%c==0)$ 为真。

注：如果说 $x$ 被 $y$ 整除，那就意味着 $x \div y$ 没有余数。

今年是第 $m$ 年，她想问你，如果从今年（包含今年）开始算起，第 $n$ 个闰年的年份是多少？

因为小可可的好奇心非常之强，所以她会问你很多次这样的问题。

输入格式

本题多组测试。

输入的第一行包含两个正整数 $C, t$，其中 $C$ 表示测试点编号，对于样例 1 满足 $C=0$，$t$ 表示测试数据组数。你可以根据 $C$ 判断数据的范围与限制条件。

接下来 $t$ 行，每行五个正整数 $m, a, b, c, n$，表意如题。

输出格式

输出包含 $t$ 行，每行一个正整数，代表你对小可可询问的回复。

0  4  
2026  4  100  400  2  
2026  4  100  400  19  
2026  1  6  12  7  
2024  2  4  8  5  

2032  
2104
2032
2034

样例1解释

对于第一组数据，第 1 个闰年是 2028 年，第 2 个闰年是 2032 年。

对于第二组数据，第 18 个闰年是 2096 年，2100 年不满足闰年条件，第 19 个闰年是 2104 年。

对于第三组数据，2026 年是第 1 个闰年，第 7 个闰年是 2032 年。

对于第四组数据，2024 年是第 1 个闰年，第 5 个闰年是 2034 年。

样例 2 ~ 6

见选手目录下的 year/year.in* 与 year/year.ans*。

样例中的 $C$ 代表这组样例对应的实际测试点，其数据范围一致。

数据范围

对于所有测试点，保证 $C, t, m, a, b, c, n$ 都为正整数，$b$ 被 $a$ 整除，$c$ 被 $b$ 整除且 $t \leq 3 \times 10^5$，$m \leq 10^{17}$，$n \leq 10^9$，$a < b < c \leq 10^8$。

提示

如果你认为程序运行时很复杂，建议使用 scanf/printf、关闭同步流、或使用选手目录提供的 year/year.cpp 模板，以优化输入输出效率。

附加样例