题目描述

译自 COCI 2022/2023 Contest #1 T4 [Lozinke]

在十年的编程生涯之后，Vinko 决定转行成为一个瓦工。他上班第一天就接到了一个十分困难的任务。

他需要给一个音乐厅铺一种正方形的陶瓷地砖。然而，他不会以瓷砖边平行于音乐厅墙壁的方式铺设，他会旋转地砖，使得地砖的对角线平行于音乐厅的墙壁。

Vinko 还没有确定他要用多大的瓷砖，但是他知道所用的瓷砖大小必须完全一致，并且他们的对角线长度应该是一个正整数。他会让放置的第一块瓷砖与最下方和左边的墙壁接触，然后剩余瓷砖都按与之前贴好的瓷砖共边的方式铺设。他将重复这一过程直到整个地面都被铺满瓷砖，整个地面大小为 $10^7 \times 10^7$。

Vinko 不仅是一个好程序员和瓦工，还是一个出色的音乐家。因此他知道地面上有 $n$ 个点对大厅的良好声学效果至关重要。如果一块瓷砖的一角的位置是这 $n$ 个点之一，大厅的声学效果将得到明显改善。

请帮 Vinko 确定对于这 $n$ 个点有多少种铺砖方式（也就是有多少种不同大小的瓷砖可以选择）满足第 $i$ 个点是某个瓷砖的一角。

输入格式

第一行包含一个整数 $n$ ($1 \le n \le 10^6$)，表示声学点个数。

接下来 $n$ 行包含两个整数 $x_i$ 和 $y_i$ ($0 \le x_i, y_i \le 10^7$)，表示第 $i$ 个点到左边墙壁的距离为 $x_i$，到下边墙壁的距离为 $y_i$。

输出格式

输出 $n$ 行，第 $i$ 行输出对于第 $i$ 个点的答案。

3
1 4
0 0
0 9

1
0
3

3
5 1
4 3
2 4

0
1
1

数据规模与约定

子任务 附加限制 分值

1 $1 \le n \le 10,000$，$0 \le x_i, y_i \le 100$ 14

2 $1 \le n \le 10,000$ 50

3 无附加限制 36