//Задача "Строки Фибоначчи-2"
//4-я Интернет-олимпиада сезона 2009-2010, усложненный уровень
//Автор задачи: Федор Царев, tsarev@rain.ifmo.ru
//Автор решения: Рустам Ганеев ganeev@rain.ifmo.ru
//Неверное решение: решение перебором всех строк


program shablon;
{$O+}
{$APPTYPE CONSOLE}
{$R+,Q+,S+}
uses
  SysUtils;

var a : array [0..45] of string;
    i, j, t, p, n, sum, ans: Longint;
begin
  reset(input,'fib2.in');
  rewrite(output,'fib2.out');
  a[0] := 'a';
  a[1] := 'b';
  sum := 1;
  read(n);
  for i := 1 to n do begin
    read(t);
    if sum < t then begin
       for j := sum + 1 to t do
        a[j] := a[j - 2] + a[j - 1];
    end;
    read(p);
    ans := 0;
    for j := 1 to p do
      if (a[t][j] = 'a') then
        inc(ans);
    writeln(ans);
  end;
end.
 