You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

题目描述

对于正整数 $n$，如果存在正整数 $m$（$m\ge 2$）使得 $n$ 是 $m^2$ 的倍数，则称 $n$ 是一个缪零数。

对于正整数 $n$，如果它不是 $2 \sim n - 1$ 中任意一个整数的倍数，则称 $n$ 是一个质数。特别的，$1$ 不是质数。

给出正整数 $n$，请问 $n$ 有多少种方法写成一个缪零数与一个质数的和？在所有方案中，缪零数和质数的差（大数减小数）最小是多少？

输入格式

输入一行一个整数 $n$。

输出格式

输出两行。

第一行一个整数，代表 $n$「写成一个缪零数与一个质数的和」的方案数。
第二行一个整数，代表在所有方案中，缪零数和质数的差（大数减小数）的最小值。

11

3
3

27

6
5

1925

170
17

提示

样例 1 解释

存在如下 $3$ 种方式，将 $11$ 写成一个缪零数与一个质数的和。

1. $11 = 2 + 9$，其中 $2$ 是质数，$9$ 是缪零数；
2. $11 = 3 + 8$，其中 $3$ 是质数，$8$ 是缪零数；
3. $11 = 7 + 4$，其中 $7$ 是质数，$4$ 是缪零数；

其中 $7, 4$ 的差最小，为 $3$。

数据规模与约定

• 对于 $30\%$ 的数据，$2 \leq n \leq 100$；
• 对于 $60\%$ 的数据，$2 \leq n \leq 500$；
• 对于 $100\%$ 的数据，$2 \leq n \leq 10000$。

保证至少存在一种方法，将 $n$ 写成一个缪零数与一个质数的和。