407530: GYM102822 K Knowledge is Power

Memory Limit:256 MB Time Limit:1 S
Judge Style:Text Compare Creator:
Submit:0 Solved:0

Description

K. Knowledge is Powertime limit per test1 secondmemory limit per test256 megabytesinputstandard inputoutputstandard output

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})$$$?

Input

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.

Output

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.

ExampleInput
4
5
6
7
10
Output
Case #1: 1
Case #2: -1
Case #3: 1
Case #4: 3

加入题单

上一题 下一题 算法标签: