MDOLLS - Nested Dolls
Tác giả: flashmt
Ngôn ngữ: Pascal
const fi='';
var test,it,n,re:longint;
a,b,f:array[1..20000] of longint;
procedure sort(l,r:longint);
var i,j,x,y,t:longint;
begin
i:=l; j:=r; x:=a[(i+j) shr 1]; y:=b[(i+j) shr 1];
repeat
while (a[i]<x) or ((a[i]=x) and (b[i]>y)) do inc(i);
while (a[j]>x) or ((a[j]=x) and (b[j]<y)) do dec(j);
if i<=j then
begin
t:=a[i]; a[i]:=a[j]; a[j]:=t;
t:=b[i]; b[i]:=b[j]; b[j]:=t;
inc(i); dec(j);
end;
until i>j;
if i<r then sort(i,r);
if l<j then sort(l,j);
end;
procedure rf;
var i:longint;
begin
read(n);
for i:=1 to n do read(a[i],b[i]);
sort(1,n);
end;
function bs(x:longint):longint;
var l,r,m,i:longint;
begin
l:=1; r:=re;
while l<=r do
begin
m:=(l+r) shr 1;
if f[m]<x then r:=m-1
else l:=m+1;
end;
for i:=m-1 to m+1 do
if (i>0) and (i<=re) and (f[i]<x) then exit(i);
end;
procedure pr;
var i,x:longint;
begin
re:=1; f[1]:=b[1];
for i:=2 to n do
if b[i]<=f[re] then
begin
re:=re+1; f[re]:=b[i];
end
else
begin
x:=bs(b[i]);
f[x]:=b[i];
end;
writeln(re);
end;
begin
assign(input,fi); reset(input);
read(test);
for it:=1 to test do
begin
rf;
pr;
end;
close(input);
end.