Alice: Hi Bob! Let's play a game.
Bob: Oh no! It's boring because both of us always choose the optimal strategy.
Alice: Well, then let's solve some Diophantine equations. What's the integer solutions of x2 + y2 = n if n is a fixed positive integer?
Bob: Er.. It's easy to get the solutions when n is a prime or 1. But it's a bit hard to solve this equation when n is a composite number.
Alice: Do you know Brahmagupta-Fibonacci identity? It says that the product of two sums each of two squares is itself a sum of two squares. Specifically: (a2 + b2)(c2 + d2) = (ac + bd)2 + (ad - bc)2 = (ac - bd)2 + (ad + bc)2. When n is a composite number, perhaps the solutions when n is a prime can be combined via this indentity.
Bob: Yes, the Brahmagupta-Fibonacci identity helps a lot. Now we can solve the equation easily. Let's solve some other equations. What about the integer solutions of x2 + y2 + z2 = A and x + y + z = B?
Alice: It's similar to the former equation but more complicated. Let's write a program to solve it.
Bob: Ok! It seems that we should get the decomposition of 3A - B2 first. And when 3A - B2 is less than zero, there cannot be any integer solutions.
Alice: I can write the prime factorization part. Can you complete the remaining part?
Bob doesn't know how to write a program. He turned to you for help. You are given two integers A and B. The prime factors of 3A - B2 will also be given. You should output all the integer solutions of x2 + y2 + z2 = A and x + y + z = B. Because of the symmetry, only the integer solutions (x, y, z) that x <= y <= z are required.
Input
There are multiple test cases. The first line of input contains an integer T (about 2000) indicating the number of test cases. For each test case:
There are two or more integers in one line. The first two integers are A (0 <= A <= 1018) and B (-109 <= B <= 109) respectively. The following integers in the same line are the prime factors of 3A - B2. If 3A - B2 is less than 2, no prime factors will be given.
Output
For each test case, output a label "Case #id:" first where id (starting from 1) is the case number. The following lines should be all the integer solutions (listed in x increasing order). For each integer solution, there should be three integer numbers x, y and z separated by a space.
You can assume that the total output will be no more than 20000 lines.
Sample Input
7
10 2 2 13
3 -3
1 1 2
15 -7
467716406 4 2 7 13 19
999278059394184698 1000000000 2 999007 999907 1000003
666666666666666645 -1 2 999999999999999967
Sample Output
Case #1:
-1 0 3
Case #2:
-1 -1 -1
Case #3:
0 0 1
Case #4:
Case #5:
-17655 8609 9050
-17641 8175 9470
-17554 7131 10427
-17494 6677 10821
-17410 6159 11255
-17215 5210 12009
-17059 4586 12477
-16773 3611 13166
-16591 3065 13530
-15954 1427 14531
-15499 426 15077
-15225 -130 15359
-14641 -1225 15870
-14323 -1779 16106
-14029 -2269 16302
-13714 -2773 16491
-13398 -3259 16661
-12966 -3895 16865
-12615 -4390 17009
-12265 -4866 17135
-11859 -5398 17261
-10585 -6945 17534
-9766 -7855 17625
-9298 -8349 17651
Case #6:
-325445947 576237380 749208567
-325096053 574086620 751009433
-324917875 573008543 751909332
-324556125 570853457 753702668
Case #7:
-641498974 163610588 477888385
