Canadian Computing Competition: 1996 Stage 1, Senior #3

Write a program that repeatedly reads two numbers ~n~ and ~k~ and prints all bit patterns of length ~n~ with ~k~ ones in descending order (when the bit patterns are considered as binary numbers). You may assume that ~0 < n \le 30~, ~0 \le k < 8~, and ~k \le n~. The first number in the input gives the number of pairs ~n~ and ~k~. The numbers ~n~ and ~k~ are separated by a single space. Leading zeroes in a bit pattern should be included. See the example below.

Sample Input

3
2 1
2 0
4 2

Sample Output

The bit patterns are
10
01

The bit patterns are
00

The bit patterns are
1100
1010
1001
0110
0101
0011

Note that the grader is sensitive with spacing and new lines. Ensure that there are spaces between output cases, but no extra one for the last case. You will recieve a WA judge verdict if the spacing is incorrect.