Enumerating Rational Numbers

#### Descriprion 下面是一段构造分数序列的伪代码： ``` for d = 1 to infinity do for n = 0 to d do if gcd(n,d) = 1 then print n / d ``` 然后根据这样的代码，就可以构造出一个无限分数的分数序列。 但是，菜菜的 $\sf\color{Gray}Shuchong$ 不知道怎么算出第 $k$ 项了。 所以他只好找强强的您来帮忙啦！ #### Input **多组数据。** 每组数据一行一个整数 $k$，如果输入为 $0$ 停止程序。 #### Output 每组数据一行两个整数 $n,d$ 代表序列的第 $k$ 项。 #### Limitation 对于 $100\%$ 的数据，$1 \le k \le 12158598919$。 #### Source Translated by 一只书虫仔。

[problemUrl]: https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=25&page=show_problem&problem=2302 [PDF](https://uva.onlinejudge.org/external/113/p11327.pdf) 



1
2
3
12158598919
0

0/1
1/1
1/2
199999/200000