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≤10^6) denoting the number of test cases. Each test case contain Input will consist of a series of numbers greater than 10 and less than 10^6, one per line
Output:
For each case, print the case number and print 3 primes P_{1}, P_{2}, P_{3} on a line, where P_{1} + P_{2}^{2} + P_{3}^{2} is equal to the number from the input. (P1, P2, P3 must be print 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 softed order.
Sample:
Input 
Output 
3 
Case 1: 2 3 5 
Note:
For second Case 20
2,3,3(2+3^{2}+3^{2}) =20 and 2,3,7 (2^{2}+3^{2}+7)=20 is possible
but 2,3,3 is the least one
hide comments
[Rampage] Blue.Mary:
20180514 05:59:57
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:

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