题目描述

只有瞬间的美才能被称为艺术。

迪达拉最近发现了一个好玩的东西——TNT!在经过一番奥妙重重的试验后,他很快就成了TNT大师。他发现TNT在爆炸时,相邻的TNT也会被间接引燃,从而形成新一轮的爆炸。即位于(x, y)的TNT爆炸后会引燃位于(x, y)、(x+1, y)、(x-1,y)、(x,y+1)、(x,y-1)的TNT。

迪达拉的下一步计划是制造一场这个世界未曾见过的爆炸,他已经在世界的各个角落放置了N个TNT。由于这些TNT很多,无法逐一点燃。于是迪达拉拿出了他的烈焰弓,他将在世界的中心,坐标为(0, 0),瞬间发出若干支箭来引燃所有的TNT。在发出一支箭后,烈焰弓会损失部分耐久值,损失的耐久值为箭飞行的距离(向下取整),即点燃位于(x, y)处的TNT需要消耗的耐久值为$\lfloor \sqrt{x^2+y^2}\rfloor$

迪达拉很爱惜他的烈焰弓,希望你能帮他算算最少需要消耗多少耐久值才能完成这场爆炸。


输入格式

第一行一个整数T $(1\le T \le 10)$,表示有T组测试数据。
对于每组测试数据:
第一行一个整数N($1\le N \le 10^5$)。
接下来N行每行两个整数x,y $(-10^9 \le x, y \le 10^9)$,表示在坐标$(x, y)$处有一个未点燃的TNT。


输出格式

对于每组测试数据,输出一行一个整数,表示点燃所有TNT需要消耗的最小耐久值。


样例数据

输入

1
3
0 0
1 0
0 8

输出

8

备注

对于样例,选择点燃(0, 0)处的TNT,消耗耐久值为0,爆炸后会自动点燃位于(1, 0)处的TNT。再点燃(0, 8)处的TNT,消耗耐久值为8,总共消耗耐久值为8。


信息

时间限制: 5s
内存限制: 128MB
评测模式: Normal

导航

比赛介绍
比赛排名
数据统计
评测状态
答疑平台
打印服务