비트 패턴 생성기

주어진 각 쌍 n, k에 대해, 길이가 n이고 정확히 k개의 1을 포함하는 모든 비트 패턴을 출력하는 프로그램을 작성하세요. 패턴은 이진수로 간주했을 때의 값이 큰 것부터 작은 것 순서(내림차순)로 출력합니다. 입력에는 여러 개의 n, k 쌍이 주어지며, 각 쌍마다 이 작업을 반복합니다.

첫 번째 줄에는 n, k 쌍의 개수 T가 주어집니다. 이어지는 각 쌍은 두 정수 n과 k로 이루어지며, 두 정수는 하나의 공백으로 구분됩니다. 모든 입력은 $0 < n \le 30$, $0 \le k < 8$, $n \ge k$를 만족합니다.

각 n, k 쌍마다 먼저 The bit patterns are라는 한 줄을 출력한 뒤, 조건을 만족하는 모든 비트 패턴을 내림차순으로 한 줄에 하나씩 출력합니다. 각 패턴은 앞자리 0(leading zero)을 포함하여 정확히 n자리로 출력해야 합니다. 연속한 두 쌍의 출력 사이에는 빈 줄을 하나 넣어 구분합니다.