問題文

高橋君は、ユークリッドの互除法というアルゴリズムを学びましたが、これがどのぐらいの速度で動くのか気になりました。

なので、以下のようなC言語のコードを書きました。

#include <stdio.h>

int counter = 0;
int gcd(int a, int b) {
    if (b == 0) return a;
    counter++;
    return gcd(b, a%b);
}

int main() {
    int a, b;
    scanf("%d %d", &a, &b);
    gcd(a, b);
    printf("%d\\n", counter);
}

これは、$2$ つの整数を標準入力から受け取り、そのgcdをユークリッドの互除法で求め、求める際に何回再帰したかを出力するコードです。

あなたは、このプログラムにいろんな値を出力させたくなりました。

具体的には、$K$ が与えられるので、このプログラムの出力が $K$ となるような $a, b$ を一組求めてください。

制約

• $1 ≦ K ≦ 40$

ただし、以下の制約を満たすテストケースにすべて正解すれば $30$ 点が与えられる。

• $1 ≦ K ≦ 10$

入力

入力は以下の形式で標準入力から与えられる。

$K$

出力

$a, b$ を空白区切りで $1$ 行に出力せよ。ただし、以下の制約を満たしていなければいけない。

$1 ≦ a, b ≦ 1,000,000,000$

入力例1

1

出力例1

1 1

入力例2

3

出力例2

4 5

入力例3

12

出力例3

314159265 358979323

どの入出力例も、これ以外にも条件を満たす出力はたくさんあります。