方程求解(Solving Equations)

题目描述

对于给定正整数 $n,m$，我们称正整数 $c$ 为好的，当且仅当存在非负整数 $x,y$，使得 $nx+my=c$。

现在给出多组数据，对于每组数据，给定 $n,m,q$，求 $[1,q]$ 内有多少个正整数不是好的。

输入格式

第一行，一个整数 $T$ 表示数据组数。

接下来每行三个正整数，分别表示 $n,m,q$，即一组询问。

输出格式

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

样例输入 #1

2
78 100 4
70 3 34

样例输出 #1

4
23

数据范围

• 对于 $30\%$ 的数据，$n,m,q\le 100$。
• 对于 $60\%$ 的数据，$n,m,q\le 10^5$。
• 对于 $100\%$ 的数据，$n\le 10^5, m\le 10^9, q\le 10^{18}, T\le 10$。

知识点与难度

本题涉及的知识点从属于 GESP 六级（数论、枚举、同余分析），难度等级：⭐⭐⭐⭐。

测试点分布