知识就是力量。小兔和小马都渴望获得更多的知识，所以他们总是互相出题考对方。今天，小兔给小马出了一个新题目。

小兔给小马一个正整数 $x$。小马需要找到一个整数集合 $S = \{a_1, a_2, \dots, a_n\}$，满足以下条件：

• $n \ge 2$
• $a_i > 1$，对于 $1 \le i \le n$
• $\sum_{i=1}^{n} a_i = x$
• 对于任意 $i \neq j$，$a_i$ 和 $a_j$ 互质

例如，如果 $x = 12$，那么 $S = \{3, 4, 5\}$、$S = \{5, 7\}$ 和 $S = \{2, 3, 7\}$ 都是合法的集合。如果两个整数的唯一公约数是 $1$，则称这两个整数互质。

我们定义 $a_{\max}$ 为 $S$ 中的最大元素，$a_{\min}$ 为 $S$ 中的最小元素。小兔希望 $(a_{\max} - a_{\min})$ 的值尽可能小。你能帮小马找到 $(a_{\max} - a_{\min})$ 的最小值吗？

输入格式

第一行包含一个整数 $T$ ($1 \le T \le 10^5$)，表示测试用例的数量。 每个测试用例包含一个整数 $x$ ($5 \le x \le 10^9$)，即小兔给小马的整数。

输出格式

对于第 $i$ 个测试用例，如果答案为 $y$，请在一行中输出 Case #i: y。如果没有可能的解，请在一行中输出 Case #i: -1。

样例

输入格式 1

4
5
6
7
10

输出格式 1

Case #1: 1
Case #2: -1
Case #3: 1
Case #4: 3