K. Knowledge is Power
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard 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 \gt 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.

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