Бяцхан Петя тоонуудын хуваагчдыг хайх дуртай. Нэгэн өдөр Петяд дараах бодлоготой дайралджээ.

Чамд $x_i \ y_i$ хэлбэртэй $n$ хүсэлт өгөгдсөн. Хүсэлт бүрд Петя $x_i$ тооны хуваагчдын хэд нь $x_{i-y_i}, x_{i- y_i + 1}, ..., x_{i - 1}$ тоонуудын алийг нь ч хуваагддаггүй болохыг тоолох шаадлагатай.

Оролт

Эхний мөрөнд $n$ ($1 ≤ n ≤ 10^5$) тоо өгөгдөнө. Дараагийн $n$ мөрөнд $x_i \ y_i$ тоонууд зайгаар тусгаарлагдан өгөгдөнө ($1 ≤ x_i ≤ 10^5$, $0 ≤ y_i  ≤ i - 1$, энд $i$ нь хэд дэх хүсэлт гэдгийг илтгэнэ).

Хэрвээ $y_i$ = 0 байвал $x$ тооны хуваагчдын тоо нь бидний хариулт болох учир өмнөх $x_i$ тоонуудыг авч үзэх шаардлагагүй.

Гаралт

Хүсэлт бүрт хариу болох $k$ тоонуудыг тус бүрт нь нэг мөрөнд хэвлэнэ. ()

Let's write out the divisors that give answers for the first 5 queries:

1) 1, 2, 4

2) 3

3) 5

4) 2, 6

5) 9, 18