有 $n$ 个球排成一行。每个球上都有一个数字，第 $i$ 个球上的数字为 $i$ ($1 \le i \le n$)。

每一轮中，我们选择索引为 $1$ 或质数的球，并按顺序将它们从队列中踢出。之后，我们开始下一轮，剩余的球保持相对位置不变，索引从 $1$ 开始重新编号（但球上的数字不会改变）。我们重复此过程，直到没有球剩下。存在一个踢出序列 $D$，初始为空。每次踢出一个球时，球上的数字就会被追加到 $D$ 中。

例如，当 $n = 6$ 时，我们有球 $[1, 2, 3, 4, 5, 6]$ 排成一行。在第一轮中，我们按顺序踢出球 $[1, 2, 3, 5]$（索引为 $1, 2, 3, 5$），剩余的球为 $[4, 6]$。在第二轮中，我们按顺序踢出 $[4, 6]$（索引为 $1, 2$），此时没有球剩下。因此，踢出序列为 $D = [1, 2, 3, 5, 4, 6]$。注意 $D$ 的索引始终从 $1$ 开始。

现在你需要回答两类问题：

• 类型 1：给定 $n$ 和 $k$，求 $k$ 在踢出序列中的索引。换句话说，找到 $x$ 使得 $D[x] = k$。
• 类型 2：给定 $n$ 和 $k$，求踢出序列中第 $k$ 个数字。换句话说，找到 $x$ 使得 $D[k] = x$。

输入格式

第一行包含一个整数 $T$ ($1 \le T \le 2 \cdot 10^5$)，表示查询次数。 接下来的 $T$ 行，每行包含三个整数 $t, n, k$ ($t \in \{1, 2\}, 1 \le k \le n \le 10^6$)，表示上述类型 $t$ 的查询。

输出格式

对于每个查询，输出一行答案。

样例

输入 1

10
1 5 1
1 5 2
1 5 3
1 5 4
1 5 5
2 5 1
2 5 2
2 5 3
2 5 4
2 5 5

输出 1

1
2
3
5
4
1
2
3
5
4