Manhattan

Time Limit: 10000 ms Memory Limit: 65536 KiB

Problem Description

 

Input

 The input contains multiple test cases. The first line of the input contains one positive integer, which is the number of test cases in the input.

Each test case begins with two positive integers, n (2 <= n <= 10^5) and d (1 <= d <= 3), indicating that their are n points in the d-dimensional space to be given. Then, n lines follow, each containing d integers. The ith of the lines contains coordinates of the ith point. All the coordinates in the input file are at most 106 in absolute value.

Output

 For each test case, output one line containing the distance between the farthest pair of points..

Sample Input

1
3 1
0
2
10

Sample Output

10

Hint

 

Source

山东省第二届ACM大学生程序设计竞赛