In mathematics, the Farey sequence of order n is the sequence of completely reduced fractions between 0 and 1 which, when in lowest terms, have denominators less than or equal to n, arranged in order of increasing size. Each Farey sequence starts with the value 0, denoted by the fraction 0/1, and ends with the value 1, denoted by the fraction 1/1 (taken from Wikipedia). For this problem we append a fraction 0/0 at the beginning of each series. So, the modified Farey sequences of order 1 to 8 are given below: F1 = F2 = F3 = F4 = F5 = F6 = F7 = F7 = {} 0,01,1 {} 0, 01, 12, 1 {} 0, 01, 13, 21, 23, 1 {} 0, 01, 14, 31, 12, 23, 34, 1 {} 0, 01, 15, 41, 13, 25, 12, 35, 32, 34, 45, 1 {} 0, 01, 16, 51, 14, 13, 25, 12, 53, 23, 34, 45, 56, 1 {} 0, 01, 17, 61, 15, 14, 27, 13, 52, 37, 12, 47, 35, 23, 57, 34, 45, 56, 67, 1 {} 0, 01, 18, 71, 16, 15, 14, 27, 31, 38, 25, 37, 12, 47, 35, 58, 23, 57, 34, 45, 56, 67, 78, 1 Now we can represent each fraction p/q as a point (q, p) in the Cartesian plane. If we connect these points in the same order of Farey sequence (additionally the last one is connected to the first) we get a polygon. In this problem such a polygon will be called Farey Polygon of magnification 1. For example if we plot the fractions of F4 in Cartesian plane and connect them in the same order as they are in the Farey sequence we get a Farey polygon of order four and magnification 1. This polygon is shown in Figure 1 (see the next page). By multiplying the coordinates of vertices of Farey Polygon of order n, and magnification 1 with an integer m (and of course then connecting them) we get a Farey Polygon of order n and magnification m. For example in Figure 2 we see a Farey Polygon of order 4 and magnification 2. The number of lattice points inside this polygon is 5. Given the number of lattice points inside a lattice polygon, you will have to find its order and magnification. Input The input file contains 12000 lines of inputs. Each line contains a non-negative integer I, which denotes the number of lattice points inside the Farey Polygon. The value of I does not exceed 1016. Input is terminated by a line containing ‘-1’. This line should not be processed. Output For each line of input produce one line of output. This line may contain two positive integers n and m that indicates the order and magnification respectively of the Farey Polygon, that has exactly I lattice
2/2 points inside it. If there is more than one answer produce the one that has the minimum positive n. If there is still a tie choose the minimum positive m. If no such Farey Polygon is found whose order and magnitude is less than 15001, then print the line ‘NOT FOUND’ (without the quotes) instead. Figue 1: Farey Polygon of order 4 and magnification 1 Sample Input 5 1 100 102 -1 Sample Output 42 13 2 11 NOT FOUND Figure 2: Farey Polygon of order 4 and magnification 2