Vampire Escape (part 1)

A vampire is trapped in a rectangular room of height $H$ and width $W$ .

There are mysterious holes in the roof: due to strange room geometry, each hole projects a circular patch of sunlight (a sunspot) onto the floor.

Thus the room contains $N$ sunspots, each represented as a circle of radius $R_{i}$ centered at coordinates $(X_{i}, Y_{i})$ . All circle centers lie strictly inside the room, i.e. $0 < X_{i} < W$ and $0 < Y_{i} < H$ . Some sunspots might intersect.

Although the room is dim, faint sunlight leaks everywhere. To minimize his exposure time, the vampire can only dash straight upward from the bottom wall to the top wall along a vertical line segment.

If this vertical path intersects or even touches any sunspot, the vampire is instantly incinerated. Otherwise, he survives and reaches the top wall.

Determine the total length of positions on the bottom wall (the line segment from $(0, 0)$ to $(W,0)$) from which the vampire can safely dash upward to the top wall without touching any sunspot.

Input

The first line contains an integer $T$ — the number of test cases.
Each test case consists of:

One line with three integers $H, W, N$ — the room’s height, width, and the number of sunspots.
$N$ following lines, each with three integers $X_{i}, Y_{i}, R_{i}$ — the coordinates and radius of the $i$ -th sunspot.

Constraints

$2 \leq H, W \leq 1000$
$1 \leq N \leq 100$
$0 < X_{i} < W$
$0 < Y_{i} < H$
$1 \leq R_{i} \leq 1000$

Output

For each test case, output a line in the form Case #i: num, where num is the total length of segments on the bottom wall from which the vampire can safely dash upward.

It can be proven that the answer is always an integer number.

Example

Input

Output

Case #1: 4
Case #2: 1
Case #3: 0

Explanation

In Case 1, the vampire can dart vertically anywhere from $(0, 0)$ to $(3, 0)$ , or from $(5, 0)$ to $(6, 0)$ , and not touch the sunspot:

case1

In Case 2, the vampire can only start between $(3, 0)$ and $(4, 0)$ :

case2

In Case 3, there is no way to get from the bottom to the top of the room:

case3