题目描述

33DAI 规定了一个上限正整数 $R$，然后定义了一个非常有意思的函数：

int f(int x, int n)
{
    if (n == 0)
        return x;
    if (x % 2 == 0)
        return f(x / 2, n - 1);
    return f(min(3 * x + 1, R), n - 1);
}

33DAI 希望你帮他算算 $Q$ 个 函数值。

输入格式

第一行为空格隔开的两个正整数 $Q,R$。

接下来 $Q$ 行，第 $i$ 行为空格隔开的两个正整数 $x_i, n_i$，描述了需要你求解的第 $i$ 个函数值的两个参数。

输出格式

输出 $Q$ 行，每行一个整数。

第 $i$ 行为第 $i$ 个函数值，即 $f(x_i, n_i)$。

10 100
33 1
33 10
33 100
33 1000
1 1
1 2
1 3
1 4 
1 5
1 6

100
44
2
2
4
2
1
4
2
1

5 1000
333 1000000
334 1000000
335 1000000
336 1000000
337 1000000

466
412
466
2
466

数据规模与约定

对于 $100\%$ 的数据，$1 \le Q,R \le 10^6$，$1\le x_i\le R$，$1\le n_i\le 10^9$。

• 子任务 1（30 分）：$1 \le Q,R,x_i,n_i \le 1000$。
• 子任务 2（30 分）：$R\le 10$。
• 子任务 3（40 分）：没有特殊限制。