# Clarke and points

Time Limit: 2000/1000 MS (Java/Others)

Memory Limit: 65536/65536 K (Java/Others)

## Description

Clarke is a patient with multiple personality disorder. One day he turned into a learner of geometric.
He did a research on a interesting distance called Manhattan Distance. The Manhattan Distance between point $A(x_A, y_A)$ and point $B(x_B, y_B)$ is $|x_A-x_B|+|y_A-y_B|$.
Now he wants to find the maximum distance between two points of $n$ points.

## Input

The first line contains a integer $T(1 \le T \le 5)$, the number of test case.
For each test case, a line followed, contains two integers $n, seed(2 \le n \le 1000000, 1 \le seed \le 10^9)$, denotes the number of points and a random seed.
The coordinate of each point is generated by the followed code.


long long seed;
inline long long rand(long long l, long long r) {
static long long mo=1e9+7, g=78125;
return l+((seed*=g)%=mo)%(r-l+1);
}

// ...

cin >> n >> seed;
for (int i = 0; i < n; i++)
x[i] = rand(-1000000000, 1000000000),
y[i] = rand(-1000000000, 1000000000);


## Output

For each test case, print a line with an integer represented the maximum distance.

## Sample Input

2
3 233
5 332

## Sample Output

1557439953
1423870062

hujie

## Source

BestCoder Round #72 (div.2)