问题描述

高桥君学习了欧几里得算法，但他很好奇这个算法的运行速度有多快。

于是，他写了以下的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);
}

该代码从标准输入中获取两个整数，使用欧几里得算法计算它们的最大公约数，并输出递归的次数。

你想让这个程序输出不同的值。

具体来说，给定一个整数 $K$，请找到一组整数 $a$ 和 $b$，使得该程序的输出为 $K$。

约束条件

• $1 ≤ K ≤ 40$

对于满足以下约束条件的测试用例，如果能正确输出，则得到30分。

• $1 ≤ K ≤ 10$

输入

输入以以下形式从标准输入中给出。

$K$

输出

以空格分隔的整数 $a$ 和 $b$。

但是，必须满足以下约束条件。

$1 ≤ a, b ≤ 1,000,000,000$

示例1

1

输出示例1

1 1

示例2

3

输出示例2

4 5

示例3

12

输出示例3

314159265 358979323

对于每个输入输出示例，都可以有很多其他满足条件的输出。