在十年的编程生涯后，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$ 个点的方案数。

子任务

样例

输入 1

3
1 4
0 0
0 9

输出 1

1
0
3

输入 2

3
5 1
4 3
2 4

输出 2

0
1
1

说明

第二个样例的说明：题目描述中的图片对应第二个样例。