Dwendwen想回家

众所周知，Dwendwen家住城堡，每天都要坐直升飞机才能回到城堡。不幸的是今天Dwendwen的直升飞机被他小伙伴拆坏了，因此只能坐车回城堡。在回家的路上他的保镖跟他汇报路上有炸弹，得全部引爆掉，不然不能回去。据消息回报，每个炸弹有3个属性，爆炸半径r，炸弹坐标(x,y)和爆炸耗费c。假如炸弹a爆炸，如果炸弹b坐标正好在炸弹a爆炸的边界内(包括边界)，那么炸弹b也会爆炸。

Dwendwen满脑子都想早点回去吃饭，因此求助于在场的各位能不能快速告诉他最少需要花费多少钱才能把炸弹全解决，如果太贵，Dwendwen可能会再买一辆直升飞机。

第一行输入一个T(1<=T<=20)，表示T个测试样例。

对于每个测试样例，第一行给出N(1<=N<=1000)。

随后每一行给出四个整数x，y，r，c。其中(-10^8<=x,y<=10^8)，(1<=r<=10^7)，(1<=c<=10^4)。

对于每个测试样例，输出引爆所有炸弹的最小花费。

1
5
0 0 1 5
1 1 1 6
0 1 1 7
3 0 2 10
5 0 1 4

15