题目内容

在二维直角坐标系中有 $n$ 个点（按输入顺序编号为 $1$∼$n$），每个点的横、纵坐标均为整数。

请你构造一个大小为 $n×n$ 的数组 {$a_{i,j}$}。对任意两个不同的编号$i,j$，将线段 $ij$ 围绕点 $i$ 旋转一周，线段的另一端点在以 $i$ 为圆心、半径为 $∣ij∣$ 的圆盘上运动。定义$a_{i,j}$ 为线段 $ij$ 在旋转过程中扫过的区域（即以$i$ 为圆心、半径为 $∣ij∣$ 的圆盘）内包含的、除 $i,j$ 之外其他编号不同的点的数量；特别地，对所有$1≤i≤n$都有 $a_{i,i}=0$。

更形式化地，令点$i$的坐标为 $(x_i,y_i)$，则：

输入描述

每个测试文件包含多组测试数据：第一行输入一个整数$T(1≤T≤10^2)$，代表数据组数。每组测试数据描述如下：

• 第一行输入一个整数 $n(1≤n≤2×10^3)$，表示点的数量。
• 此后共 $n$ 行，每行输入两个整数 $x,y(1≤x,y≤10^9)$，表示一个点的坐标，按输入顺序依次编号为 $1,2,…,n$。

除此之外，保证单个测试文件的 $n$ 之和不超过 $2×10^3$。

输出描述

对于每一组测试数据，输出$n$ 行：

• 第$i$行输出 $n$ 个整数，依次为 $a_{i,1},a_{i,2},…,a_{i,n}$；
• 数与数之间以一个空格分隔。

样例1

输入

2
3
1 1
2 1
1 2
4
1 1
2 1
3 1
4 1

输出

0 1 1
0 0 1
0 1 0
0 0 1 2
1 0 1 2
2 1 0 1
2 1 0 0