P9031 [COCI 2022/2023 #1] Iksevi

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

Vinko 需要使用正方形瓷砖铺满音乐厅的地板。他不会让瓷砖的边与墙壁平行；相反，他选择让瓷砖的对角线与墙壁平行。 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$，即声学关键点的数目。 接下来 $n$ 行，每行两个整数 $x_i,y_i$，表示第 $i$ 个声学关键点与左侧墙壁与后方墙壁的距离。

输出 $n$ 行，每行一个整数。 第 $i$ 行表示能使 $i$ 号声学关键点位于瓷砖角落的瓷砖尺寸数。

| 子任务 | 分值 | 数据范围 | | :-----------: | :-----------: | :-----------: | | $1$ | $15$ | $1\leq n \leq 10^4,0\leq x_i,y_i \leq 100$ | | $2$ | $55$ | $1\leq n \leq 10^4,0\leq x_i,y_i \leq 10^7$ | | $3$ | $40$ | $1\leq n \leq 10^6,0\leq x_i,y_i \leq 10^7$ | 本题满分 $110$ 分。