NAJBB - Boss Baby

Boss Baby is the boss of all babies. He has been exploring prime numbers lately, and new recently made a conjecture resembling one of Goldbach's conjectures. Boss baby’s conjecture is that any number greater than or equal 10 can be expressed as the sum of a prime, square of two prime. It’s very easy work for him but he is busy to stop the dastardly plot of the CEO of Puppy Co.  He wants your help verify his conjecture for small numbers.

Note: 1 is not a prime number.

Input

The first line of the input contains an integer T (T ≤ 106) denoting the number of test cases. Each test case will consist of a number greater than 10 and less than 106, one per line.

Output

For each case, print the case number and the 3 primes P1, P2, P3 on a line, where P1 + P22 + P32 is equal to the number from the input. (P1, P2, P3 must be printed in sort order.) If no such primes exist, print "0 0 0" instead (quotes for clarity). If there are multiple triplets of primes that satisfy the equation, print the least one in sorted order.

Sample

Input:
3
18
20
23

Output:
Case 1: 2 3 5
Case 2: 2 3 3
Case 3: 3 3 5

Note

For second Case 20

  • 2, 3, 3 (2 + 32 + 32) = 20
  • 2, 3, 7 (22 + 32 + 7) = 20
are possible, but 2, 3, 3 is the least one


Added by:Najmuzzaman
Date:2017-05-06
Time limit:2s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All

hide comments
2018-05-14 05:59:57 [Rampage] Blue.Mary
I think the problem requires to output 3 prime numbers p<=q<=r for a input number x, such that at least one of the following is satiesfied:
p*p+q*q+r = x
p*p+q+r*r = x
p+q*q+r*r = x
among all possible triples (p,q,r), choose the smallest p, then smallest q, then smallest r.
If no triple exists output three zeroes.

If the above assuption is correct, please make sure your test data is right.

->Najmuzzaman: I am change the Data Set. Please Try Now.

Last edit: 2018-05-14 10:39:57
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.