Shuchong 与 ClCN 的分数序列

Descriprion

$\sf\color{Gray}Shuchong$ 很菜，他想构造一个分数序列，然而他构造不出来，所以只好找强强的 $\sf C\color{Red}lCN$ 帮忙，$\sf C\color{Red}lCN$ 明显不屑于构造简单的分数序列，所以扔给了 $\sf\color{Gray}Shuchong$ 一个构造分数序列的方法：

在 $[1,\infty]$ 枚举 $d$：
$\ \ \ \$在 $[0,d]$ 枚举 $n$：
$\ \ \ \ \ \ \ \$如果 $\gcd(n,d)=1$：
$\ \ \ \ \ \ \ \ \ \ \ \$在分数序列中添加一个分数 $\dfrac{n}{d}$

然后根据这样的步骤，就可以构造出一个无限分数的分数序列。

但是，菜菜的 $\sf\color{Gray}Shuchong$ 不知道怎么算出第 $n$ 项了。
所以他只好找强强的您来帮忙啦！

Input

多组数据。
每组数据一行一个整数 $k$，如果输入为 $0$ 停止程序。

Output

每组数据一行两个整数 $n,d$ 代表序列的第 $k$ 项。

Limitation

对于 $100\%$ 的数据，$1 \le k \le 12158598919$。

Source

Translated by 一只书虫仔。

Shuchong 与 ClCN 的分数序列

#### Descriprion

$\sf\color{Gray}Shuchong$ 很菜，他想构造一个分数序列，然而他构造不出来，所以只好找强强的 $\sf C\color{Red}lCN$ 帮忙，$\sf C\color{Red}lCN$ 明显不屑于构造简单的分数序列，所以扔给了 $\sf\color{Gray}Shuchong$ 一个构造分数序列的方法：

> 在 $[1,\infty]$ 枚举 $d$：    
> $\ \ \ \ $在 $[0,d]$ 枚举 $n$：   
> $\ \ \ \ \ \ \ \ $如果 $\gcd(n,d)=1$：   
> $\ \ \ \ \ \ \ \ \ \ \ \ $在分数序列中添加一个分数 $\dfrac{n}{d}$

然后根据这样的步骤，就可以构造出一个无限分数的分数序列。

但是，菜菜的 $\sf\color{Gray}Shuchong$ 不知道怎么算出第 $n$ 项了。   
所以他只好找强强的您来帮忙啦！

#### Input

**多组数据。**   
每组数据一行一个整数 $k$，如果输入为 $0$ 停止程序。

#### Output

每组数据一行两个整数 $n,d$ 代表序列的第 $k$ 项。

#### Limitation

对于 $100\%$ 的数据，$1 \le k \le 12158598919$。

#### Source

Translated by 一只书虫仔。