1.
import java.util.BitSet;
import java.util.Scanner;

/**
* Angewandte Mathematik, SS11
* Problem: 729 - The Hamming Distance Problem
* Link: http://uva.onlinejudge.org/external/7/729.pdf
*
* @author Benedikt Zšnnchen
* @author Erik Wenzel
* @version 1.0, 29/04/2011
*
* Method : brute force, BitSet extended, decimal => dual calculation
* Status : Accepted
* Runtime: 1.888
*/
public class Main
{
public static void main(String[] args)
{
int n, h, cases, maxVariation;
Scanner sc = new Scanner(System.in);
EBitSet bits;
cases = sc.nextInt();

for(int i = 0; i < cases; i++)
{
n = sc.nextInt();
h = sc.nextInt();
maxVariation = (int)Math.pow(2, n);

for (int j = 0; j < maxVariation; j++)
{
bits = new EBitSet(j, n); // 16 ist max!
if (bits.getSetCount() == h)
{
System.out.println(bits);
}
}
if(i<cases-1)
{
System.out.println();
}
}
}

/**
* Calculate the binomial coefficient n over k
* @param n
* @param k
* @return return n over k
*/
public static long getBinomialCoefficient(int n, int k)
{
if(n == k || n == 0 || k == 0)
{
return 1;
}

if(k>n)
{
k=n-k;
}

return getBinomialCoefficient(n-1, k) + getBinomialCoefficient(n-1, k-1);
}
}

/**
* Erweitert das BitSet um die Eigenschaft mit Integerwerten initialisiert
* zu werden und um eine besserer Ausgabe/Formatierung
* @author Benedikt Zšnnchen
*
*/
class EBitSet extends BitSet
{
private int size;
private int minSize;

/**
* Standardkonstruktor
* @param value wird ins dualsystem umgewandelt
*/
public EBitSet(int value)
{
super();
setValue(value);
}

/**
* @param value
* @param minSize fŸr Blockausgabe
*/
public EBitSet(int value, int minSize)
{
super();
setValue(value);
this.minSize = minSize;
}

private void setValue(int value)
{
this.clear();
int i = value;
int bIndex = 0;
while(i > 0)
{
if(i % 2 == 1)
{
this.set(bIndex);
}
bIndex++;
i = i >> 1;
}
size=bIndex;
if(minSize<size)
{
minSize = size;
}
}

public int getSetCount()
{
int index = -1;
int counter = 0;
while((index = nextSetBit(++index))!=-1)
{
counter++;
}
return counter;
}

@Override
public int size()
{
return size;
}

public int getMinSize()
{
return minSize;
}

@Override
public String toString()
{
String out = "";
for(int i = getMinSize()-1; i >= 0; i--)
{
out += get(i)?"1":"0";
}
return out;
}
}