問題文

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

なので、以下のような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

入力例1

1

出力例1

1 1

入力例2

3

出力例2

4 5

入力例3

12

出力例3

314159265 358979323

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