{"raw_statement":[{"iden":"background","content":"写了十年的代码后，Vinko 决定转行做一名陶艺家。他在新工作的第一天就接到了一项艰巨的任务。"},{"iden":"statement","content":"Vinko 需要使用正方形瓷砖铺满音乐厅的地板。他不会让瓷砖的边与墙壁平行；相反，他选择让瓷砖的对角线与墙壁平行。\n\nVinko 还没有决定他将使用的瓷砖大小，但他知道所有瓷砖必须大小相同，而且对角线的长度必须是一个正偶数。\n\nVinko 铺下的第一块瓷砖的角将与左侧和后方的墙接触。此后他铺下的每一块瓷砖都与至少一块已铺好的瓷砖有一条边重合。他将重复这以一过程，直到铺满整个 $10^7 \\times 10^7$ 平方毫米的地面。\n\n除了程序员和陶艺家，Vinko 也是一个优秀的音乐家。正因为如此，他知道地板上有 $n$ 个点对大厅的音响效果至关重要。如果瓷砖的角落位于 $n$ 个点中的一个，大厅的声学效果将显著改善。\n\n![](https://cdn.luogu.com.cn/upload/image_hosting/o4bbstj2.png)\n\n如图，左图为瓷砖对角线长度为 $4$ 的铺装，在此条件下，点 $(2,4)$ 在瓷砖的角落上，此时它满足条件，使得音响效果大为改善，但点 $(4,3)$ 和 $(5,1)$ 不满足条件。右图则为瓷砖对角线长度为 $2$ 的铺装，此时点 $(4,3)$ 在四块瓷砖的角落，而点 $(2,4)$ 和 $(5,1)$ 不在。\n\n帮助 Vinko 确定对于 $n$ 个点中的每个点，有多少种瓷砖尺寸可以使铺满地面后第 $i$ 个点位于瓷砖的角落上。"},{"iden":"input","content":"第一行包含一个整数 $n$，即声学关键点的数目。\n\n接下来 $n$ 行，每行两个整数 $x_i,y_i$，表示第 $i$ 个声学关键点与左侧墙壁与后方墙壁的距离。"},{"iden":"output","content":"输出 $n$ 行，每行一个整数。\n\n第 $i$ 行表示能使 $i$ 号声学关键点位于瓷砖角落的瓷砖尺寸数。"},{"iden":"note","content":"| 子任务 | 分值 | 数据范围 |\n| :-----------: | :-----------: | :-----------: |\n| $1$ | $15$ | $1\\leq n \\leq 10^4,0\\leq x_i,y_i \\leq 100$ |\n| $2$ | $55$ | $1\\leq n \\leq 10^4,0\\leq x_i,y_i \\leq 10^7$ |\n| $3$ | $40$ | $1\\leq n \\leq 10^6,0\\leq x_i,y_i \\leq 10^7$ |\n\n本题满分 $110$ 分。"}],"translated_statement":null,"sample_group":[["3\n1 4\n0 0\n0 9","1\n0\n3"],["3\n5 1\n4 3\n2 4","0\n1\n1"]],"show_order":[],"formal_statement":null,"simple_statement":null,"has_page_source":false}