DWITE, January 2012, Problem 5

Comets have recently passed through your region of space, leaving behind a trail of dust. You would like to get a rough idea of the extent of this pollution, by finding the two most distant dust particles. Here, we define distance as the sum of differences between the ~x~, ~y~, and ~z~ coordinates. For example, the distance between two particles at ~(1, 4, 9)~ and ~(4, 4, 4)~ is ~3 + 0 + 5 = 8~.

There are ~N~ comets, and we describe each comet with ~11~ numbers: ~(A, B, C)~, ~(D, E, F)~, ~(G, H, I)~, and ~(U, V)~. A comet's position at time ~t~ is given by ~(At^2 + Bt + C, Dt^2 + Et + F, Gt^2 + Ht + I)~. A comet leaves behind a particle of dust at every integer time ~t~ between ~U~ and ~V~, inclusive.

For example, consider a comet described by ~(1, 0, 0)~, ~(0, -2, 1)~, ~(0, 0, 6)~, and ~(1, 5)~. It leaves behind 5 dust particles, at ~(1, -1, 6)~, ~(4, -3, 6)~, ~(9, -5, 6)~, ~(16, -7, 6)~, and ~(25, -9, 6)~. The first and last points are the most distant pair, with distance ~24 + 8 + 0 = 32~.

Pay close attention to the bounds. You may assume that there will be fewer than ~100\,000~ dust particles, and that all positions will fit within a signed 32-bit integer.

~1 \le N \le 100~

~-500 \le A, D, G, U, V \le 500~

~-100\,000 \le B, C, E, F, H, I \le 100\,000~

~U \le V~

The input will contain 5 test cases. Each will begin with a single integer ~N~. ~N~ lines will follow, each containing ~11~ integers, in the order described above.

The output will contain 5 lines of output, one integer for each test case: the distance between the most distant pair of dust particles. There will be at least 2 dust particles.

Sample Input

1
1 0 0 0 -2 1 0 0 6 1 5
3
3 1 4 1 5 9 2 6 5 3 58
2 7 1 8 2 8 1 8 2 8 45
1 6 1 8 0 3 3 9 8 8 74

Sample Output

32
66726

Problem Resource: DWITE