Description

It is well known thatπ≈22/7.You can verify that for all integers p and q satisfying 1<=q<=7 and p/q ≠ 22/7, we have |22 - 7π| < |p - qπ|. Furthermore, 355/133 is another good approximation of π.You can also verify that for all integers p and q satisfying 1<=q<=113 and p/q ≠ 355/113, we have |355 - 113π| < |p - qπ|.

Let p, q, x, y, x1 and y1 be integers, α be a real number and q > 0. We say that y/x is d-closer to αthan y1/x1 if |y - xα| < |y1 - x1α|. Notice that if α is also a rational number p/q, then the inequality |yq - xp| < |y1q - x1p| is equivalent to |y - xα| < |y1 - x1α| . This can be used to avoid oating point operations. If y/x is d-closer to αthan any other rational number y1/x1 with denominator x1 in the range from 1 to x, then y/x is called a good approximation of α. Let G(α) be the set of all good approximations α and |G(α) | be the cardinality of G(α). The cardinality of a set G(α) is the number of elements in G(α). We use an example to illustrate these symbols. Let α=37/13. The good approximations of α are 3/1,17/6 and 37/13. The rational number 3/1 is a good approximation of α since no other rational number with denominator 1 and an integer numerator is d-closer to α than 17/6. A similar reason holds for 37/13. It is clear that no rational number with denominator greater than 6 and an integer numerator is d-closer to α than 37/13 since |37 - 13α| =0. Therefore, G(α)={3/1, 17/6, 37/13} and |G(α) |=3. Similarly, you can fi nd that G(237/113)={2/1, 21/10, 65/31, 86/41, 237/113} and |G(237/113) |=5.

Given a rational number α, you are asked to design a program for finding |G(α) |.

Input

The first line of the input file contains an integer n, n<=10, which represents the number of test cases. Then, the cases are listed line by line. In each line, there are two integers pk and qk separated by a space which are the numerator and denominator, respectively, of test case k, k = 1, 2,...,n. Note that 1 <= pk, qk <= 10000.

Output

List the value of |G(pk/qk) | in line k for k = 1, 2,...,n.

2
37 13
237 113

3
5

Source

Taiwan 2001