#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int MAX_N = 1e5 + 5;
const ll INF = (ll) 2e18 + 5;
struct Point {
int x[2];
ll CalculateDist(const Point &other) const {
ll ans = 0;
for(int i = 0; i < 2; i++) {
ans += 1ll * (x[i] - other.x[i]) * (x[i] - other.x[i]);
}
return ans;
}
bool operator!= (const Point &other) const {
for(int i = 0; i < 2; i++) {
if(x[i] != other.x[i]) {
return true;
}
}
return false;
}
};
struct ComparePoints {
private:
int axis;
public:
ComparePoints(int axis = 0) {
this -> axis = axis;
}
bool operator () (const Point &p1, const Point &p2) const {
return p1.x[axis] < p2.x[axis];
}
};
struct Node {
private:
Point p;
int axis;
int value;
Node *left;
Node *right;
public:
Node() {
this -> left = nullptr;
this -> right = nullptr;
}
void Build(Point *points, int le, int ri, int axis) {
if(le > ri) {
return;
}
else if(le == ri) {
this -> p = points[le];
this -> left = nullptr;
this -> right = nullptr;
return;
}
int mid = (le + ri) / 2;
nth_element(points + le, points + mid, points + ri, ComparePoints(axis));
this -> value = points[mid].x[axis];
this -> axis = axis;
this -> left = new Node();
this -> right = new Node();
this -> left -> Build(points, le, mid, (axis ^ 1));
this -> right -> Build(points, mid + 1, ri, (axis ^ 1));
}
ll FindNearestNeighbour(Point qPoint) {
if(this == nullptr) {
return INF;
}
else if(this -> left == nullptr && this -> right == nullptr) {
if(this -> p != qPoint) {
return this -> p.CalculateDist(qPoint);
}
return INF;
}
ll ansLeft = INF, ansRight = INF;
if(qPoint.x[this -> axis] <= this -> value) {
ansLeft = this -> left -> FindNearestNeighbour(qPoint);
if(qPoint.x[this -> axis] + sqrt(ansLeft) >= this -> value) {
ansRight = this -> right -> FindNearestNeighbour(qPoint);
}
}
else {
ansRight = this -> right -> FindNearestNeighbour(qPoint);
if(qPoint.x[this -> axis] - sqrt(ansRight) <= this -> value) {
ansLeft = this -> left -> FindNearestNeighbour(qPoint);
}
}
return min(ansLeft, ansRight);
}
};
Node *root;
Point ps[MAX_N], startPoints[MAX_N];
int main() {
int cntTests;
scanf(" %d", &cntTests);
for(int cs = 1; cs <= cntTests; cs++) {
int n;
scanf(" %d", &n);
for(int i = 0; i < n; i++) {
scanf(" %d %d", &ps[i].x[0], &ps[i].x[1]);
startPoints[i] = ps[i];
}
root = new Node();
root -> Build(ps, 0, n - 1, 0);
for(int i = 0; i < n; i++) {
printf("%lld\n", root -> FindNearestNeighbour(startPoints[i]));
}
printf("\n");
}
return 0;
}
I2luY2x1ZGUgPGJpdHMvc3RkYysrLmg+CiNkZWZpbmUgbGwgbG9uZyBsb25nCnVzaW5nIG5hbWVzcGFjZSBzdGQ7Cgpjb25zdCBpbnQgTUFYX04gPSAxZTUgKyA1Owpjb25zdCBsbCBJTkYgPSAobGwpIDJlMTggKyA1OwoKc3RydWN0IFBvaW50IHsKCWludCB4WzJdOwoKCWxsIENhbGN1bGF0ZURpc3QoY29uc3QgUG9pbnQgJm90aGVyKSBjb25zdCB7CgkJbGwgYW5zID0gMDsKCQkKCQlmb3IoaW50IGkgPSAwOyBpIDwgMjsgaSsrKSB7CgkJCWFucyArPSAxbGwgKiAoeFtpXSAtIG90aGVyLnhbaV0pICogKHhbaV0gLSBvdGhlci54W2ldKTsJCgkJfQoKCQlyZXR1cm4gYW5zOwoJfQoKCWJvb2wgb3BlcmF0b3IhPSAoY29uc3QgUG9pbnQgJm90aGVyKSBjb25zdCB7CgkJZm9yKGludCBpID0gMDsgaSA8IDI7IGkrKykgewoJCQlpZih4W2ldICE9IG90aGVyLnhbaV0pIHsKCQkJCXJldHVybiB0cnVlOwoJCQl9CgkJfQoKCQlyZXR1cm4gZmFsc2U7Cgl9Cn07CgpzdHJ1Y3QgQ29tcGFyZVBvaW50cyB7Cglwcml2YXRlOgoJCWludCBheGlzOwoJCglwdWJsaWM6CgkJQ29tcGFyZVBvaW50cyhpbnQgYXhpcyA9IDApIHsKCQkJdGhpcyAtPiBheGlzID0gYXhpczsKCQl9CgkKCQlib29sIG9wZXJhdG9yICgpIChjb25zdCBQb2ludCAmcDEsIGNvbnN0IFBvaW50ICZwMikgY29uc3QgeyAKCQkJcmV0dXJuIHAxLnhbYXhpc10gPCBwMi54W2F4aXNdOwoJCX0KfTsKCnN0cnVjdCBOb2RlIHsKCXByaXZhdGU6CgkJUG9pbnQgcDsKCQlpbnQgYXhpczsKCQlpbnQgdmFsdWU7CgkKCQlOb2RlICpsZWZ0OwoJCU5vZGUgKnJpZ2h0OwoJCglwdWJsaWM6CgkJTm9kZSgpIHsKCQkJdGhpcyAtPiBsZWZ0ID0gbnVsbHB0cjsKCQkJdGhpcyAtPiByaWdodCA9IG51bGxwdHI7CgkJfQoKCQl2b2lkIEJ1aWxkKFBvaW50ICpwb2ludHMsIGludCBsZSwgaW50IHJpLCBpbnQgYXhpcykgewoJCQlpZihsZSA+IHJpKSB7CgkJCQlyZXR1cm47CgkJCX0KCQkJZWxzZSBpZihsZSA9PSByaSkgewoJCQkJdGhpcyAtPiBwID0gcG9pbnRzW2xlXTsKCQkJCXRoaXMgLT4gbGVmdCA9IG51bGxwdHI7CgkJCQl0aGlzIC0+IHJpZ2h0ID0gbnVsbHB0cjsKCQkJCQoJCQkJcmV0dXJuOwoJCQl9CgoJCQlpbnQgbWlkID0gKGxlICsgcmkpIC8gMjsKCQkJbnRoX2VsZW1lbnQocG9pbnRzICsgbGUsIHBvaW50cyArIG1pZCwgcG9pbnRzICsgcmksIENvbXBhcmVQb2ludHMoYXhpcykpOwoKCQkJdGhpcyAtPiB2YWx1ZSA9IHBvaW50c1ttaWRdLnhbYXhpc107CgkJCXRoaXMgLT4gYXhpcyA9IGF4aXM7CgkJCQoJCQl0aGlzIC0+IGxlZnQgPSBuZXcgTm9kZSgpOwoJCQl0aGlzIC0+IHJpZ2h0ID0gbmV3IE5vZGUoKTsKCQkJCgkJCXRoaXMgLT4gbGVmdCAtPiBCdWlsZChwb2ludHMsIGxlLCBtaWQsIChheGlzIF4gMSkpOwoJCQl0aGlzIC0+IHJpZ2h0IC0+IEJ1aWxkKHBvaW50cywgbWlkICsgMSwgcmksIChheGlzIF4gMSkpOwoJCX0KCgkJbGwgRmluZE5lYXJlc3ROZWlnaGJvdXIoUG9pbnQgcVBvaW50KSB7CgkJCWlmKHRoaXMgPT0gbnVsbHB0cikgewoJCQkJcmV0dXJuIElORjsKCQkJfQoJCQllbHNlIGlmKHRoaXMgLT4gbGVmdCA9PSBudWxscHRyICYmIHRoaXMgLT4gcmlnaHQgPT0gbnVsbHB0cikgewoJCQkJaWYodGhpcyAtPiBwICE9IHFQb2ludCkgewoJCQkJCXJldHVybiB0aGlzIC0+IHAuQ2FsY3VsYXRlRGlzdChxUG9pbnQpOwoJCQkJfQoKCQkJCXJldHVybiBJTkY7CgkJCX0KCgkJCWxsIGFuc0xlZnQgPSBJTkYsIGFuc1JpZ2h0ID0gSU5GOwoJCQlpZihxUG9pbnQueFt0aGlzIC0+IGF4aXNdIDw9IHRoaXMgLT4gdmFsdWUpIHsKCQkJCWFuc0xlZnQgPSB0aGlzIC0+IGxlZnQgLT4gRmluZE5lYXJlc3ROZWlnaGJvdXIocVBvaW50KTsKCgkJCQlpZihxUG9pbnQueFt0aGlzIC0+IGF4aXNdICsgc3FydChhbnNMZWZ0KSA+PSB0aGlzIC0+IHZhbHVlKSB7CgkJCQkJYW5zUmlnaHQgPSB0aGlzIC0+IHJpZ2h0IC0+IEZpbmROZWFyZXN0TmVpZ2hib3VyKHFQb2ludCk7CgkJCQl9CgkJCX0KCQkJZWxzZSB7CgkJCQlhbnNSaWdodCA9IHRoaXMgLT4gcmlnaHQgLT4gRmluZE5lYXJlc3ROZWlnaGJvdXIocVBvaW50KTsKCgkJCQlpZihxUG9pbnQueFt0aGlzIC0+IGF4aXNdIC0gc3FydChhbnNSaWdodCkgPD0gdGhpcyAtPiB2YWx1ZSkgewoJCQkJCWFuc0xlZnQgPSB0aGlzIC0+IGxlZnQgLT4gRmluZE5lYXJlc3ROZWlnaGJvdXIocVBvaW50KTsKCQkJCX0KCQkJfQoKCQkJcmV0dXJuIG1pbihhbnNMZWZ0LCBhbnNSaWdodCk7CgkJfQp9OwoKTm9kZSAqcm9vdDsKUG9pbnQgcHNbTUFYX05dLCBzdGFydFBvaW50c1tNQVhfTl07CgppbnQgbWFpbigpIHsKCWludCBjbnRUZXN0czsKCXNjYW5mKCIgJWQiLCAmY250VGVzdHMpOwoKCWZvcihpbnQgY3MgPSAxOyBjcyA8PSBjbnRUZXN0czsgY3MrKykgewoJCWludCBuOwoJCXNjYW5mKCIgJWQiLCAmbik7CgoJCWZvcihpbnQgaSA9IDA7IGkgPCBuOyBpKyspIHsKCQkJc2NhbmYoIiAlZCAlZCIsICZwc1tpXS54WzBdLCAmcHNbaV0ueFsxXSk7CgkJCXN0YXJ0UG9pbnRzW2ldID0gcHNbaV07CgkJfQoKCQlyb290ID0gbmV3IE5vZGUoKTsKCQlyb290IC0+IEJ1aWxkKHBzLCAwLCBuIC0gMSwgMCk7CgoJCWZvcihpbnQgaSA9IDA7IGkgPCBuOyBpKyspIHsKCQkJcHJpbnRmKCIlbGxkXG4iLCByb290IC0+IEZpbmROZWFyZXN0TmVpZ2hib3VyKHN0YXJ0UG9pbnRzW2ldKSk7CgkJfQoKCQlwcmludGYoIlxuIik7Cgl9CgoJcmV0dXJuIDA7Cn0K