Ước Số Riêng Của Petya

Cho $n$ truy vấn được đánh số từ $1$ đến $n$. Truy vấn thứ $i$ gồm hai số nguyên $x_i$ và $y_i$.

Với mỗi truy vấn, hãy đếm số ước dương của $x_i$ mà không chia hết cho bất kỳ giá trị nào trong dãy $x_{i-y_i},x_{i-y_i+1},\dots ,x_{i-1}$.

Nói cách khác, đếm số nguyên dương $k$ sao cho:

• $k$ là ước của $x_i$, và
• $k$ không chia hết bất kỳ giá trị $x_j$ nào với $i-y_i\le j\le i-1$.

Nếu $y_i=0$ thì đáp án là tổng số ước dương của $x_i$ (không cần xét các giá trị $x$ trước đó).

Dữ liệu vào

• Dòng đầu tiên chứa một số nguyên $n$.
• $n$ dòng tiếp theo, dòng thứ $i$ chứa hai số nguyên $x_i$ và $y_i$ cách nhau bởi dấu cách.

Dữ liệu ra

In ra $n$ dòng, mỗi dòng là đáp án cho một truy vấn theo thứ tự nhập vào.

Ràng buộc

• $1\le n\le {10}^5$
• $1\le x_i\le {10}^5$
• $0\le y_i\le i-1$

Ví dụ