CNZ lives in the forest, and he has energy stones, numbered from to .
CNZ need to eat energy generated by energy stones.

The energy stone initially contains units of energy and will increase units of energy each second.
The maximum energy of energy stone is , the stone's energy stops increasing once it reach .

Each time he absorbs the energy of a continuous interval of stone. For example, if CNZ absorbs the energy of [S, T] stones, all energy stones numbered from to will become zero units of energy. CNZ can get the sum of energy in this range.

CNZ will eat times. The i-th eating happens after seconds, and eat interval is .

What's the total amount of energy CNZ has eaten after eating.

The first line of the input gives the number of test cases, .  test cases follow.
Each test case starts with a line containing the integer , the number of energy stones.
Then, there are  more lines, the i-th of which contains the three integers ,  and  as described above.
The next line contains one integer M.
Then, there are  more lines, the i-th of which contains the three integers ,  and  as described above.

Limits:

For each test case, output one line containing Case #x: y, where x is the test case number (starting from 1) and y is the result.

1
4
2 1 4
2 2 5
2 1 10
2 3 2
2
1 1 4
4 2 3

Case #1: 20

At t = 0s, the energy of each energy stone: [2 2 2 2]

At t = 1s, the energy of each energy stone: [3 4 3 2]. CNZ eats 3+4+3+2 energy. The energy of each energystone will be: [0 0 0 0].

At t = 2s, the energy of each energy stone: [1 2 1 2].

At t = 3s, the energy of each energy stone: [2 4 2 2].

At t = 4s, the energy of each energy stone: [3 5 3 2]. CNZ eats 5+3 energy. The energy of each energy stone will be: [3 0 0 2].

The answer of this example is: (3+4+3+2)+(5+3)=20