const
  mm=1000007;
  p=23;
var
f:array[0..1000007]of boolean;
s,sum:array[0..2000]of longint;
m,n,i,j,t,t0,now,min,ans,k:longint;

function mmiinn(a,b:longint):longint;
begin
    if a>b then exit(b);
    exit(a);
end;

function suan(i:longint):longint;
begin
    suan:=(sum[n]-sum[i-1] shl (n-i+1)) shl (i-1);
    suan:=suan+sum[i-1];
end;

procedure chelk;
var
n0,i:longint;
begin
    i:=1;n0:=0;
    while s[i]=0 do begin
        inc(i);inc(n0);
    end;
    i:=n;
    while s[i]=0 do begin
        dec(i);inc(n0);
    end;
    if n0>k then exit;
    min:=mm;
    for i:=1 to n do
        sum[i]:=sum[i-1]*2+s[i];
    for i:=1 to n do
        min:=mmiinn(min,suan(i));
    min:=min mod mm;
    if not f[min] then begin
        f[min]:=true;
        inc(ans);
    end;
end;

procedure sou(i:longint);
var
n0:longint;
begin
    if i>n then chelk
    else begin
        n0:=now;
        s[i]:=1;
        now:=0;
        sou(i+1);
        s[i]:=0;
        now:=n0+1;
        if now<=k then sou(i+1);
        now:=n0;
    end;
end;

begin
    assign(input,'01ring.in');reset(input);
    assign(output,'01ring.out');rewrite(output);
    read(t0,m);
    for t:=1 to t0 do begin;
        fillchar(f,sizeof(f),false); ans:=0;
        read(n,k);
        ans:=0;
        sou(1);
        if k>=n then inc(ans);
        writeln(ans);
    end;
    close(input);close(output);
end.