{"raw_statement":[{"iden":"statement","content":"In number theory, Goldbach's conjecture states that every even integer greater than $2$ is the sum of two prime numbers. A weaker version of this conjecture states that every odd number greater than $5$ is the sum of three prime numbers.\n\nHere is an ultra weak version of Goldbach's conjecture: every integer greater than $11$ is the sum of $textbf(s i x)$ prime numbers. Can you help to verify or disprove this conjecture?\n\nThe first line of the input gives the number of test cases, $T$ ($1 <= T <= 200$). $T$ test cases follow.\n\nEach test case contains one integer $N$ ($1 <= N <= 10^(12)$).\n\nFor each test case, output \"_Case x:_\" first, where _x_ is the test case number (starting from $1$). If the solution exist, output six prime numbers separated by spaces; otherwise output \"IMPOSSIBLE\" (quotes for clarity) when the solution does not exist. When the solution exists, any valid solution is acceptable.\n\n"},{"iden":"input","content":"The first line of the input gives the number of test cases, $T$ ($1 <= T <= 200$). $T$ test cases follow.Each test case contains one integer $N$ ($1 <= N <= 10^(12)$)."},{"iden":"output","content":"For each test case, output \"_Case x:_\" first, where _x_ is the test case number (starting from $1$). If the solution exist, output six prime numbers separated by spaces; otherwise output \"IMPOSSIBLE\" (quotes for clarity) when the solution does not exist. When the solution exists, any valid solution is acceptable."}],"translated_statement":null,"sample_group":[],"show_order":[],"formal_statement":"**Definitions**  \nLet $ n, m \\in \\mathbb{Z} $ denote the number of stations and public railway edges, respectively.  \nLet $ A = (A_1, A_2, \\dots, A_n) \\in \\{0,1\\}^n $, where $ A_i = 0 $ if station $ i $ belongs to JR West, and $ A_i = 1 $ if JR East.  \nLet $ G = (V, E) $ be the undirected graph of public railways, with $ V = \\{1, 2, \\dots, n\\} $ and $ E $ of size $ m $, representing bidirectional public edges.  \nPrivate railways exist between all pairs of stations within the same JR region (i.e., complete subgraphs on $ \\{i \\mid A_i = 0\\} $ and $ \\{i \\mid A_i = 1\\} $).  \n\n**Constraints**  \n1. $ 1 \\le n \\le 10^5 $, $ 0 \\le m \\le 10^5 $  \n2. $ G $ is connected.  \n3. No duplicate public edges.  \n\n**Objective**  \nFor each station $ i \\in \\{1, \\dots, n\\} $, compute:  \n$$\nS_i = \\sum_{j=1}^{n} D(i, j)\n$$  \nwhere $ D(u, v) $ is the minimum number of tickets required to travel from $ u $ to $ v $, with the following rules:  \n- Traveling along a **private railway** (same JR region) costs **0 tickets**.  \n- Traveling along a **public railway** costs **1 ticket**.  \n- Switching regions via a public edge incurs 1 ticket.  \n- The cost of a path is the number of public edges used.  \n\nThus, $ D(u, v) $ is the shortest path in $ G $, where edge weights are 1 for public edges and 0 for private edges (implicitly complete within regions).","simple_statement":"Given n stations and m public train lines, each station is owned by JR West (0) or JR East (1). Private lines connect all stations of the same company. Rikka uses tickets for public lines, and passes (ICOCA/Suica) for private lines (free). Find, for each station, the sum of minimum tickets needed to reach all other stations.","has_page_source":false}