Pattern Generator

Write a program that, for each given pair n and k, prints every bit pattern of length n that contains exactly k ones. The patterns are printed in descending order of their value when interpreted as binary numbers. The input contains several n, k pairs, and the task is repeated for each pair.

The first line contains T, the number of n, k pairs. Each pair consists of two integers n and k separated by a single space. Every input satisfies $0 < n \le 30$, $0 \le k < 8$, and $n \ge k$.

For each n, k pair, first print the line The bit patterns are, then print every valid bit pattern in descending order, one per line. Each pattern must be printed with exactly n digits, including leading zeroes. Separate the outputs of two consecutive pairs with a single blank line.