因为在上学期的期末考中取得了优异的成绩，小C进入了重点班。她发现她的很多同班同学对自己的成绩都有很高的要求。而一旦没有达到自己的目标，他们就会自闭，然后退出重点班。为了简化问题，我们做出如下假设：
1. 每个同学对自己的要求用一个正整数ai描述，表示考得比自己差的人不能少于(全班总人数-1)/ai。
2. 每次考试的成绩取决于每个人的能力值bi，能力值越大成绩越高（能力值相同则成绩相同）。
3. 每次考试后，所有没有达到自己要求的同学同时退出。
小C很想知道，每名同学会在第几次考试后退出。
第1行包括一个正整数n，表示重点班的初始人数。
第2行到第n+1行，每行包括两个正整数ai，bi。
对于每个人输出一行一个整数，表示Ta会在第几次考试后退出；如果Ta永远不会退出，输出0。
1≤n≤105
1≤ai,bi≤109
数据保证，所有大于1的正整数在ai中至多出现2次。