wzk很喜欢欧几里得算法。欧几里得算法是一种用来求最大公约数的常用算法，它的一种 C++ 递归实现如下：
int gcd(int a, int b) { if (b == 0) { return a; } else { return gcd(b, a % b); } }
现在我们已知 gcd(a, b) 这个函数共递归了 次，求所有满足 的可能的 中 最小的一组的 与 之和。
gcd(a, b)
你需要处理 组询问，也就是对 个不同的 给出 各自 的 的最小值。
第一行一个正整数 ，表示共有 组询问。
接下来 行，每行一个非负整数 。
输出 行，每行一个整数，表示 的最小值。
1 0
1
1 1
3
提示：
对于样例1，考虑 gcd(1, 0) ，由于 ，不会递归，即是递归 次。
gcd(1, 0)
对于样例2，考虑 gcd(2, 1) ，会递归一次至 gcd(1, 0) 。
gcd(2, 1)