Overlapping Air Traffic Control Zones

Optimization of air traffic flow is one of the essential ways for airlines to maintain economic viability. All too often, however, weather and other anomalous conditions disrupt air traffic flow resulting in significant costs. Automation systems for optimizing flows are not currently able to quickly reconfigure when path planning must account for dynamic conditions such as moving weather systems. Human intervention is usually used to decide route modifications.

Decisions on route modification for one aircraft must take into account neighboring aircraft safe zones in order to minimize possible collision risks. We will consider a 3D model in which the safe zone for one aircraft is represented as a parallelepiped.

Evaluation of aircraft collision risks, in this model, can be done by calculating the volume of the intersecting safe zones of the aircrafts in a given air traffic control zone. In other words, we need to be able to determine the volume of intersecting parallelepipeds.

Problem

Consider a number of parallelepipeds in space, having all the edges parallel to the axes. Your task is to write a program that outputs the volume occupied simultaneously by two or more parallelepipeds. Each parallelepiped is characterized by 6 integer values, the coordinates of two of its vertices

(x₁,y₁,z₁), (x₂, y₂,z₂) with x₁ < x₂, y₁ < y₂ and z₁ < z₂

Input

The input file contains several test cases, each of them consists of an integer 0 ≤ n ≥ 15 in the first line followed by n lines of 6-tuples of integers describing the parallelepipeds. The total area occupied does not exceed 5x10⁸.

Output

For each test case, output on a line by itself an integer corresponding to the total volume occupied simultaneously by two or more parallelepipeds.

Sample Input

  5
 1 1 3 3 3
   1 1 1 3 3 3
   1 1 1 3 3 3
   400000000 400000000 400000000 400000001 400000001 400000002
   400000000 400000000 400000000 400000002 400000004 400000001 

Sample Output

  9