You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

题目背景

写了十年的代码后，ln决定转行做一名陶艺家。他在新工作的第一天就接到了一项艰巨的任务。

题目描述

ln需要使用正方形瓷砖铺满音乐厅的地板。他不会让瓷砖的边与墙壁平行；相反，他选择让瓷砖的对角线与墙壁平行。

ln还没有决定他将使用的瓷砖大小，但他知道所有瓷砖必须大小相同，而且对角线的长度必须是一个正偶数。

ln铺下的第一块瓷砖的角将与左侧和后方的墙接触。此后他铺下的每一块瓷砖都与至少一块已铺好的瓷砖有一条边重合。他将重复这以一过程，直到铺满整个 $10^7 \times 10^7$ 平方毫米的地面。

除了程序员和陶艺家，ln也是一个优秀的音乐家。正因为如此，他知道地板上有 $n$ 个点对大厅的音响效果至关重要。如果瓷砖的角落位于 $n$ 个点中的一个，大厅的声学效果将显著改善。

如图，左图为瓷砖对角线长度为 $4$ 的铺装，在此条件下，点 $(2,4)$ 在瓷砖的角落上，此时它满足条件，使得音响效果大为改善，但点 $(4,3)$ 和 $(5,1)$ 不满足条件。右图则为瓷砖对角线长度为 $2$ 的铺装，此时点 $(4,3)$ 在四块瓷砖的角落，而点 $(2,4)$ 和 $(5,1)$ 不在。

帮助 ln确定对于 $n$ 个点中的每个点，有多少种瓷砖尺寸可以使铺满地面后第 $i$ 个点位于瓷砖的角落上。

输入格式

第一行包含一个整数 $n$，即声学关键点的数目。

接下来 $n$ 行，每行两个整数 $x_i,y_i$，表示第 $i$ 个声学关键点与左侧墙壁与后方墙壁的距离。

输出格式

输出 $n$ 行，每行一个整数。

第 $i$ 行表示能使 $i$ 号声学关键点位于瓷砖角落的瓷砖尺寸数。

样例 #1

样例输入 #1

3
1 4
0 0
0 9

样例输出 #1

1
0
3

样例 #2

样例输入 #2

3
5 1
4 3
2 4

样例输出 #2

0
1
1

提示

本题满分 $110$ 分。