You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

题目描述

有 $T$ 次询问，每次给出三个数 $x,y,z$，请你求出一个数 $\bmod x$ 的值为 $y$，则其 $\bmod z$ 的值有多少种不同的可能性。

输入格式

第一行一个正整数 $T$。

接下来 $T$ 行每行 $3$ 个数表示 $x,y,z$。

输出格式

输出 $T$ 行，每行一个非负整数，表示答案。

样例 #1

样例输入 #1

1
33 22 11

样例输出 #1

1

提示

对于所有数据，保证 $0 \le y < x \le 10^{18},1 \le z \le 10^{18},1 \le T \le 10^5$。

对于前 20% 的数据，保证 $1 \le x,z \le 10$。

对于前 40% 的数据，保证 $1 \le x,z \le 10^8$。

对于另外 10% 的数据，保证 $x=1$ 或 $z=1$。

对于另另外 10% 的数据，保证 $y=0$。