var
 Zad : Word;
 iZad : Word;
 pPocTok, pPocZn, pZnOdk : array [1..65000] of Word;
 iPole, MaxPole, PoleSize : Word;
 NumL,NumA : Word;
 DoRead:Boolean;
 OdkazLen : Word;
 
begin
 Readln(Zad);
 MaxPole := 65000;
 for iZad := 1 to Zad do begin
{
  Writeln('Cisteni ',iZad);
  for iPole := 1 to MaxPole do begin
   pPocTok[iPole] := 0;
   pPocZn[iPole] := 0;
   pZnOdk[iPole] := 0;
  end;
}
  DoRead := true;
  PoleSize := 0;
  Writeln('Zadani ',iZad,':');
  while DoRead do begin
   Read(NumL); Readln(NumA);
   if not((NumL=0) and (NumA=0)) then begin
    Inc(PoleSize);
    pPocTok[PoleSize] := 0;
    pPocZn[PoleSize] := NumL;
    pZnOdk[PoleSize] := NumA;
    iPole := PoleSize;
    while (iPole>1) and (pPocTok[PoleSize]<250001) do begin
     Dec(iPole);
     if pZnOdk[iPole]>0 then begin
      if pZnOdk[iPole]>NumL then Dec( pZnOdk[iPole] , NumL )
       else pZnOdk[iPole] := 0;
      Inc( pPocTok[PoleSize] );
     end;
    end;
    Writeln(pPocTok[PoleSize]);
   end else
    DoRead := false;
  end; (* DoRead *)
  MaxPole :=PoleSize;
  Writeln;
  
 end;  (* for iZad *)
{ Writeln('Hotovo!');}
end.