# Coprimes

How many times must a man look up Before he can see the sky? Yes, ‘n’ how many ears must one man have Before he can hear people cry? Yes, ‘n’ how many deaths will it take till he knows That too many people have died? The answer, my friend, is blowin’ in the wind, The answer is blowin’ in the wind. Another gloomy day has begun for Shahriar but as usual his CD player is singing a song of hope. He has a large piece of paper in front of him on which he is trying to partition a number into some co-prime numbers by hand in as many ways as possible and surely things are getting out of his control. He wants to write a program to do this but his limited programming ability is not helping his cause. He has already thought about asking Mr. Kisman to write a code for him but as he has already asked too many favors from him he is looking for help from another source. Can you help him? A group of numbers is co-prime when the GCD of any two of them is 1. Shahriar has decided to give a party to all those who will solve this problem so he definitely wants an efficient and intelligent solution so that number of people in the party is small and of course his budget is limited :). Input The first line of the input file is an integer N (0 < N < 40), which indicates how many sets of inputs are there. Each of the next N lines contains one set of input. Each line contains two integers S (0 < S ≤ 100) and t (0 < t ≤ 30). So your job is to partition S into t co-prime numbers. Output For each line of input you should give several lines of outputs. The description of output for each line of input is given in the paragraph below: First line should be the serial of the output. Next lines should contain all possible partitions of S into t co-prime numbers. Each line should contain one possible partition. In a partition the printed numbers should be ordered in non-decreasing order and two consecutive numbers should be separated by a single space. The partitions should be printed in ascending order. Let say one partition is P1 = a1, a2, . . . , an and another partition is P2 = b1,b2,...,bn. ak and bk are not equal and for all value of i (0 < i < k) ai =bi. ThenpartitionP1 >P2 iffak >bk andP1 <P2 iffak <bk. Therecanbearound15000lines in the output file in total. Sample Input 2 40 6 83

2/2 Sample Output Case 1: 1 1 1 1 1 35 1 1 1 1 5 31 1 1 1 1 7 29 1 1 1 1 11 25 1 1 1 1 13 23 1 1 1 1 17 19 1 1 1 3 5 29 1 1 1 3 11 23 1 1 1 5 9 23 1 1 1 5 11 21 1 1 1 5 13 19 1 1 1 7 11 19 1 1 1 7 13 17 1 1 1 9 11 17 1 1 3 5 7 23 1 1 3 5 11 19 1 1 3 5 13 17 1 1 3 7 11 17 1 1 5 7 9 17 1 1 5 9 11 13 1 3 5 7 11 13 Case 2: 116 125 134