题目描述

生日在二月二十九号的小可可常常嘀咕道：“今年为什么不是闰年呀！” 她对闰年的判断方式感到十分的不满，于是找到了你。

她规定了三个依次递增的正整数 $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$ 行，每行一个正整数，代表你对小可可询问的回复。

输入输出样例 #1

输入 #1

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

输出 #1

2032
2104
2032
2034

说明/提示

样例解释

对于样例 $1$： 第一组数据，第 $1$ 个闰年是 $2028$ 年，第 $2$ 个闰年是 $2032$ 年。 第二组数据，第 $18$ 个闰年是 $2096$ 年，$2100$ 年不满足闰年条件，第 $19$ 个闰年是 $2104$ 年。 第三组数据，$2026$ 年是第 $1$ 个闰年，第 $7$ 个闰年是 $2032$ 年。 第四组数据，$2024$ 年是第 $1$ 个闰年，第 $5$ 个闰年是 $2034$ 年。

数据范围

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

提示

• 如果你认为程序运行时限较紧，建议使用 scanf/printf或者关闭同步流，以优化输入输出效率。