program poj1925;
var
  f,x,y:array[0..1000000] of int64;
  t,n:int64;
  i,j:longint;
function min(a,b:int64):int64;
begin
  if a<b then exit(a) else exit(b);
end;
begin
  readln(t);
  while t>0 do
  begin
    readln(n);
    for i:=1 to n do readln(x[i],y[i]);
    for i:=0 to x[n] do f[i]:=maxlongint;
    f[x[n]]:=0;
    for i:=n downto 1 do
      for j:=x[i] downto x[i]-trunc(sqrt(sqr(y[i])-sqr(y[i]-y[1]))) do
      begin
        if j<0 then break;
        if j+2*(x[i]-j)>x[n] then f[j]:=1
        else f[j]:=min(f[j],f[j+2*(x[i]-j)]+1);
      end;
    if f[0]=maxlongint then f[0]:=-1;
    writeln(f[0]);
    dec(t);
  end;
end.