本题没有可用的提交语言。

P1377. 良好近似问题

问题描述

已知 π ≈ 22/7。可以验证，对于所有满足 1 ≤ q ≤ 7 且 p/q ≠ 22/7 的整数 p 和 q，有 |22 - 7π| < |p - qπ|。同样，355/113 是 π 的另一个良好近似。可以验证，对于所有满足 1 ≤ q ≤ 113 且 p/q ≠ 355/113 的整数 p 和 q，有 |355 - 113π| < |p - qπ|。

设 p, q, x, y, x1 和 y1 是整数，α 是一个实数，且 q > 0。我们称 y/x 比 y1/x1 更接近 α（d-closer），如果 |y - xα| < |y1 - x1α|。注意，如果 α 是一个有理数 p/q，则不等式 |yq - xp| < |y1q - x1p| 等价于 |y - xα| < |y1 - x1α|。这可以用来避免浮点运算。如果 y/x 比所有分母 x1 在 1 到 x 范围内的其他有理数 y1/x1 更接近 α，则称 y/x 是 α 的一个良好近似。设 G(α) 是所有良好近似的集合，|G(α)| 是 G(α) 的基数（即集合中元素的数量）。我们用一个例子来说明这些符号。例如，α = 37/13 的良好近似包括 3/1、17/6 和 37/13。3/1 是 α 的良好近似，因为在分母为 1 的所有有理数中，没有比 3/1 更接近 α 的。类似地，37/13 是良好近似，因为 |37 - 13α| = 0。因此，G(α) = {3/1, 17/6, 37/13}，|G(α)| = 3。同样，可以发现 G(237/113) = {2/1, 21/10, 65/31, 86/41, 237/113}，|G(237/113)| = 5。

给定一个有理数 α，你需要设计一个程序来计算 |G(α)|。

输入

输入文件的第一行包含一个整数 n（n ≤ 10），表示测试用例的数量。接下来是 n 行，每行包含两个整数 pk 和 qk，分别是有理数的分子和分母，k = 1, 2, ..., n。注意，1 ≤ pk, qk ≤ 10000。

输出

对于每个测试用例 k（k = 1, 2, ..., n），输出 |G(pk/qk)| 的值。

输入示例 1

2
37 13
237 113

输出示例 1

3
5

来源

Taiwan 2001

如果需要进一步帮助，请告诉我！