407530: GYM102822 K Knowledge is Power

Knowledge is power. Little Rabbit and Little Horse both long for more knowledge, so they always challenge each other to some quizzes. Today, Little Rabbit creates a new quiz for Little Horse.

Little Rabbit gives Little Horse a positive integer $$$x$$$. Little Horse needs to find a set of integers $$$S=\{a_1,a_2,\dots,a_n\}$$$ that meets the following conditions.

• $$$n \ge 2$$$
• $$$a_i>1$$$, for $$$1 \le i \le n$$$
• $$$\sum_{i=1}^na_i=x$$$
• $$$a_i$$$ and $$$a_j$$$ are co-prime, for any $$$i \neq j$$$

For example, if $$$x=12$$$, then $$$S=\{3,4,5\}$$$ and $$$S=\{5,7\}$$$ and $$$S=\{2,3,7\}$$$ are all valid sets. Two integers are said to be co-prime if the only positive integer that evenly divides both of them is $$$1$$$.

We define $$$a_{\max}$$$ as the maximum element of $$$S$$$, and $$$a_{\min}$$$ as the minimum element of $$$S$$$. Little Rabbit wants the value of $$$(a_{\max}-a_{\min})$$$ to be as small as possible. Can you help Little Horse to find the minimum value of $$$(a_{\max}-a_{\min})$$$?

The first line of the input contains an integer $$$T$$$ ($$$1 \le T \le 10^5$$$) — the number of test cases.

Each test case contains an integer $$$x$$$ ($$$5 \le x \le 10^9$$$) — the integer Little Rabbit gives to Little Horse.

For the $$$x$$$-th test case, if the answer is $$$y$$$, output $$$Case$$$ #$$$x$$$: $$$y$$$ in a single line. If there's no possible solution, output $$$Case$$$ #$$$x$$$: -$$$1$$$ in a single line.

4
5
6
7
10

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