题目描述

译自 COCI 2022/2023 Contest #1 T4「Iksevi」

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

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

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

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

左图展示了使用对角线长度为 $4$ 的瓷砖铺地面。点 $(2,4)$ 是一块瓷砖的一角，因此声学效果是好的，但是对于 $(4,3)$ 和 $(5,1)$ 就不是这样。

右图展示了使用对角线长度为 $2$ 的瓷砖铺地面。点 $(4,3)$ 是一块瓷砖的一角，因此声学效果是好的，但是对于 $(2,4)$ 和 $(5,1)$ 就不是这样。

请帮 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

数据范围与提示

子任务附加条件及分值如下表所示。