这是一个交互式问题。

给你一个整数 $n$。你的程序在 $0$ 到 $n - 1$（含）之间选择一个数字 $x$。交互器会向你提出形如“$x$ 模 $y$ 的余数是多少”的询问，其中 $y$ 是询问的参数。

交互器并不愚蠢，它不会向你提出一个答案已经预先确定的询问（即答案可以从之前询问的答案以及隐藏数字在 $0$ 到 $n - 1$ 之间这一事实中推导出来）。例如，如果交互器询问你 $x$ 模 $10$ 的余数，而你回答 $6$，那么交互器就不会再询问 $x$ 模 $2$ 的余数，因为可以推导出余数一定是 $0$。

你希望交互器能用尽可能少的询问次数得知你选择的数字。显然，你可以自适应地回答，并在过程中动态改变所选的数字，但它必须与之前的回答保持一致。

在交互开始时，你选择一个整数 $k$，并隐式地做出声明：“交互器最多通过 $k$ 次询问就能得知所选的数字”。你应该选择最小的 $k$，使得你总是能做到这一点。准确地说，令 $K$ 表示满足该条件的最小可能值。

如果你选择的 $k > K$，交互器会告知你这一点。你可以接受这个事实，或者选择角色反转。只有当你确信自己的程序没有错误（提示：其实有错），且作者的解法或测试数据存在问题时，你才应该选择角色反转。此时交互器将选择数字，而你将尽可能慢地去猜它。如果你成功进行了 $k$ 次有效的询问，你将获得 Check Failed 并证明你的观点。

如果 $k \le K$，则开始猜数环节。交互器将不断进行询问，直到它得知该数字。如果交互器能够进行 $k + 1$ 次询问，说明你没有兑现你的声明，将获得 WA。否则，你将通过该测试点。注意，如果你选择的 $k < K$，交互器通过最优的询问策略，总是能够进行至少 $k + 1$ 次询问（然而并不能保证交互器一定会这么做，请参考第三个样例）。

输入格式

你应当读取一个整数 $n$（$2 \le n \le 10^5$）。

在此之后，你应当做出你的声明。输出一个整数 $k$（$1 \le k \le 10^5$）。接下来有两种可能：

1. 如果 $k \le K$，交互器会输出 1。你选择一个数字 $x$，交互器开始猜数。

   你应当重复读取一个整数 $y$（$2 \le y \le 10^9$）并输出 $x \bmod y$，直到遇到 $y = -1$ 或 $y = 0$，或者交互器进行了第 $k + 1$ 次询问。$y = -1$ 意味着你的回答是不自适应/不一致的。$y = 0$ 意味着交互器已经知道了该数字，你通过了测试。第 $k + 1$ 次询问意味着你没有兑现你的声明。在这三种情况下，你的程序都应当终止。

2. 如果 $k > K$，交互器会输出 0。

   重复输出一个整数 $y$（$2 \le y \le 10^9$）并读取一个整数 $r$，表示 $x \bmod y$。你的询问必须是有效的（你不能预先知道答案）。如果某个询问无效，交互器将输出 -1 代替余数，且你的程序应当终止。当你得知隐藏的数字，或者你直接接受你的程序是错误的事实时，输出 -1 并终止程序。如果你进行了 $k$ 次有效的询问（这极不可能发生），你将获得 Check Failed 或类似的反馈。

注意，$-1$ 和 $0$ 是信号值，它们超出了普通 $y$ 值所使用的范围 $[2, 10^9]$。

样例

输入样例 1

3
1
15
0

输出样例 1

1
0

输入样例 2

6
1
2
5
0

输出样例 2

2
1
0

输入样例 3

100
1
80
0

输出样例 3

1
76

说明

在第一个样例中，过程如下：

• 程序读取 $n$，其等于 $3$。
• 程序输出 $k = 1$。
• 可以证明 $K = 1$。
• 交互器输出 1 并开始猜数。
• 交互器提出一个 $y = 15$ 的询问。
• 程序回答 0。
• 交互器得知隐藏的数字为 $0$ 并输出 -1。

在第二个样例中，发生了类似的过程，除了 $k = K = 2$。因此交互器进行了两次询问而不是一次。隐藏的数字是 $5$。

在第三个样例中，$K > 1$，但程序输出了 $k = 1$。然而，交互器提出了一个询问，使得在程序回答后隐藏的数字（$76$）已被确定，因此程序仍然通过了测试。如果交互器转而提出一个 $y = 10$ 的询问，程序将无法通过测试，因为在回答该询问后，隐藏数字仍然会有多种可能性。

实际的交互器可能会提出与样例中不同的询问。因此，无法通过某种占位符程序轻松通过这些样例。