#P2202. Set

Set

WarmingWarming!!Warming!!!...<o:p></o:p>

一大波考研狗来袭...<o:p></o:p>

有这样一些集合S1,S2...Sn,对于集合Si中有ai个元素。

(0<n<10000,0=<ai<=2000),所有集合中元素总个数不超过2000.

现在无聊的Yougth想知道,从这些集合里面取出来一些数,每个集合中元素至多被取一个,使得取出的元素构成一个严格递增的序列,当然取数的顺序也应该是按照集合的编号从小到大的,问取出的序列的最大长度。

Input

第一行一个数t,表示t组测试数据(t<105)。
接下来一个n,表示集合中元素的总个数。
接下来一行,每两个数(ai,bi)表示第i个元素所处集合和元素大小。

Output

一行,序列最大长度。

Sample Input

1
5
1 4 2 1 2 2 3 2 4 3

Sample Output

</p>
3

HINT

Source