405716: GYM102055 C GCD Land

GCD land consists of $$$N$$$ cities initially labeled from $$$1$$$ to $$$N$$$. Two cities are connected by a highway if GCD (greatest common divisor) of their labels is greater than 1. For example, initially city $$$4$$$ is connected with city $$$6$$$, and there is no direct highway between city $$$4$$$ and city $$$7$$$.

As the president of GCD land, Mr. Panda doesn't want his nation to be divided into disconnected pieces. Mr. Ang, the wise prime minister of the nation, suggests to increase the label of each city by a non-negative magic number $$$X$$$, such that after reconnecting the highways according to cities' new labels, the whole nation is connected. For example, if Mr. Panda increases all cities' labels by $$$8$$$, city $$$4$$$ will be connected with both city $$$6$$$ and city $$$7$$$, because $$$\gcd(12, 14)>1$$$ and $$$\gcd(12, 15) > 1$$$.

Can you help Mr. Panda find the magic number $$$X$$$ when it should be lower than $$$10^{N}$$$? If no such $$$X$$$ exists, output $$$-1$$$ instead.

The first line of input gives the number of test cases $$$T$$$ ($$$1 \le T \le 20$$$). $$$T$$$ test cases follow. Each test case contains one integer $$$N$$$ ($$$1\le N\le 10^{5}$$$), the number of cities in GCD land. For at least 75% test cases, it is guaranteed that $$$N \leq 5 \times 10^{4}$$$.

For each test case, output one line containing "Case x: y", where x is the test case number (starting from $$$1$$$), y is the non-negative magic number if the solution exists, otherwise output $$$-1$$$ instead. Any valid solution will be accepted.

2
6
30

Case 1: -1
Case 2: 151060