AT_arc051_b.[ARC051B] 互除法

高桥君学习了欧几里得算法，他很好奇它能以多快的速度运行。

因此，他写了以下代码。

#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);
}

这个代码输入两个整数，然后用欧几里得计算它们的 $\gcd$，然后输出它递归了多少次的代码。 你想让这个程序输出各种各样的值。

具体来说，输入一个 $K$，输出一组可以使得这个程序的输出为 $K$ 的 $A$、$B$。

一个正整数 $K$。

一行，两个正整数 $A$ 和$B$。

但是，必须满足 $1\le A,B\le 10^9$。

对于 $30\%$ 的数据，$1\le K \le 10$；

对于 $100\%$ 的数据，$1\le K \le 40$。

只输出其中一种可能的解即可。