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.
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);
```
For each test case, print a line with an integer represented the maximum distance.