#P2136. 最低的惩罚

最低的惩罚

那么现在问题就来了。。。

给你N(1=<N<=15)个任务,每个任务有一个截止完成时间t(1=<t<=10^8)和完成该任务需要的天数v(1=<v<=10^8),任务每超时一天惩罚加1,问最少能获得多少惩罚?

惩罚!!!咦~~~

Input

第一行一个数T,表示测试数据组数(T<2000);
对于每组测试数据,第一行一个数N,表示任务个数;
紧接着N行,每行两个数t和v,如上所述。

Output

对于每组测试数据,输出最小惩罚。

Sample Input

2
3
3 3
20 1
3 2
3
3 3
6 3
6 3 

Sample Output

2
3

HINT

Source