var t,l,i,j,m,n:longint;
    ans:int64;
begin
  readln(t);
  for l:=1 to t do
  begin
    readln(n,m);
    ans:=0;
    for i:=m downto 1 do
    begin
      ans:=ans+(n mod 2);
      n:=n div 2;
      if (n=0) then break;
    end;
    ans:=ans+n;
    writeln(ans);
  end;
end.