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² + Bt + C, Dt² + Et + F, Gt² + 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 100000 dust particles, and that all positions will fit within a signed 32-bit integer.

1 ≤ N ≤ 100

-500 ≤ A, D, G, U, V ≤ 500

-100000 ≤ B, C, E, F, H, I ≤ 100000

U ≤ V

The input file DATA5.txt 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 file OUT5.txt 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.

 
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
		        

 
32
66726