A partition of positive integer m into n components is any sequence a₁ ... a_n of positive integers such that a₁ + ... + a_n = m and a₁ ≤ a₂ ≤ ... ≤ a_n. Your task is to determine the partition, which occupies the k-th position in the lexicographic order of all partitions of m into n components.

The lexicographic order is defined as follows: sequence a₁ ... a_n comes before b₁ ... b_n iff there exists such an integer i, 1 ≤ i ≤ n, that a_j=b_j for all j, 1 ≤ j< i, and a_i< b_i.

Input

The input begins with the integer t, the number of test cases. Then t test cases follow.

For each test case the input consists of three lines, containing the positive integers m, n and k respectively (1 ≤ n ≤ 10, 1 ≤ m ≤ 220, k is not larger than the number of partitions of m into n components).

Output

For each test case output the ordered elements of the sought partition, separated by spaces.

Example

Input:  1  9  4  3    Output:  1 1 3 4