飙车赛

有n个赛车正在进行紧张刺激的飙车大赛，它们的比赛跑道为互相平行的直线。第i个赛车的起跑位置为x_i，并且每个赛车的起跑位置互不相同。比赛开始后，它们能在瞬间加速到最大速度Vi。并一直保持最大速度

你的任务是算出在赛道足够长情况下，本次飙车大赛的比赛过程中最多能有多少次超车。

有多组数据。

每组数据第一行为一个整数n，代表赛车的数量
接下来的n行，每行两个整数x_i和v_i，代表一辆赛车的起跑位置和最大速度。
赛车的信息按照起跑位置xi的升序顺序给出，即x₁<x₂<x₃<…<x_n。
最后一组数据n=0，标志着输入的结束，不需要处理。

1<=n<=250000

0≤x_i≤10⁶

^0<v_i<100

对于每组测试数据，输出一个整数，代表超车次数对10⁶取模的结果。

4
0 2
2 1
3 8
6 3
0

2