该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

时间限制：1000 ms；空间限制：256 MiB。

题目描述

小 N 最初有一堆石子，这堆石子的大小为 $n$。

一次操作中，小 N 可以选择一堆大小大于 $1$ 的石子，把它分成两堆大小均为正整数的石子。操作可以持续进行，直到所有石子堆的大小均为 $1$。

如果一次操作所选择的石子堆大小是质数，那么称这次操作为一次“质数堆操作”。

小 N 需要回答以下问题：

1. 在所有合法的完整分堆过程中，质数堆操作的最大次数是多少？
2. 在所有达到上述最大次数的完整分堆过程中，是否存在一种过程，使得过程中的某个时刻至少出现过一堆大小为 $k$ 的石子？初始大小为 $n$ 的石子堆也属于分堆过程，因此当 $k=n$ 时视为已经出现。

给定操作类型 $opt$：

• 当 $opt=1$ 时，只回答问题 1；
• 当 $opt=2$ 时，同时回答问题 1 和问题 2。

输入格式

在文件 pile.in 中读入。

第一行一个整数 $opt$。

• 若 $opt=1$，第二行一个整数 $n$；
• 若 $opt=2$，第二行两个整数 $n,k$。

输出格式

在文件 pile.out 中输出。

• 若 $opt=1$，输出一行一个整数，表示问题 1 的答案；
• 若 $opt=2$，第一行输出问题 1 的答案，第二行输出 1 或 0。存在满足问题 2 要求的最优分堆过程时输出 1，否则输出 0。

样例

样例输入 #1

1
5

样例输出 #1

4

样例输入 #2

2
5 4

样例输出 #2

4
0

样例输入 #3

2
1919 810

样例输出 #3

1757
1

样例 1 解释

对于样例 1，一种最优过程是先把 $5$ 分成 $2$ 和 $3$，再把产生的质数堆继续分开。被选择进行分堆的质数堆大小依次可以为 $5,2,3,2$，共进行 $4$ 次质数堆操作。

对于样例 2，问题 1 的答案是 $4$。若要求过程中出现大小为 $4$ 的堆，则能够获得的质数堆操作次数最多为 $3$，不能保持全局最优值，因此第二行输出 0。

数据范围

• $opt\in\{1,2\}$；
• $1\le n\le 7\times10^4$；
• 当 $opt=2$ 时，$1\le k\le n$。

本题共 $20$ 个测试点，每点 $5$ 分。