1291: 种田的大学问

​ 最近坏坏的出题人玩到了一款有趣的休闲种田游戏。在其中有一种神奇的农作物叫做土豆，在收获一支成熟的土豆时我们有概率可以获得多个土豆。无聊的出题人查看了游戏的源代码，惊讶的发现这个概率并不是随机的，其可以推导出一个具体的满判定的公式，只要土豆种下的地块坐标（x, y) 满足，（x * 9 + y * 13 + 游戏当前天数 + 游戏存档种子）% 1170289951 = 1170289950。那么我们在收获土豆时就一定可以获得最多的满满16个土豆。可爱的xjj对你提出了问题，他会告诉你n个不同的地块坐标(x[i], y[i])，他希望你可以帮他确定一个游戏存档种子，使得他可以尽早的将所有的土豆收获（使得收获完所有土豆的游戏当前天数尽可能小），注意，只有当达成满判的条件时xjj才会去收土豆。

​ 注：游戏的天数从1开始，没有第0天，同时游戏存档种子是从0 到 1170289950 之间的 一个非负整数。

​ 第一行输入一个正整数t，代表t次询问，每次询问你要解决xjj的一个问题

​ 每个询问的第一行输入一个整数 $n(1\leq n \leq 200000)$，表示种植土豆的地块数量。

​ 每个询问的第二行到第n + 1行输入 $n$ 个整数对 $x[i], y[i](1 \le x[i], y[i] \le 500)$,代表每个土豆种植的地块坐标，一个坐标可能会种植多株土豆。

​ 输入保证 $\sum n\le2\times10^5$。

​ 对于每个询问输出一个整数 root 代表你求出的能够最早收获所有土豆的游戏存档种子，$(0 \leq root \leq 1170289950)$

1
4
10 100
9 17
64 3
88 144

1170287285