题目描述

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

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

输入格式

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

输出格式

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

2
78 100 4
70 3 34

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≤10$。