Hanging Hats

All mages wear pointed hats. At the Unheard University, before going to bed each mage hangs their hat on one very large shared wall. Hats come in only two shapes: wide and narrow.

The mages fall asleep one after another. Before going to bed, the $i$-th mage takes their hat, picks an arbitrary position $(x_i, y_i)$ on the wall (where $y_i > 0$ is the height above the ground), hammers a nail there, and hangs the hat on that nail.

The hats are magical: once hung, a hat looks exactly like an isosceles triangle of height $y_i$. Its apex is at the nail $(x_i, y_i)$ and its bottom edge lies on the floor (the line $y = 0$). A narrow hat has a bottom edge of length $y_i$; a wide hat has a bottom edge of length $2 y_i$. Equivalently, a point $(x, y)$ lies inside the $i$-th hat, boundary included, exactly when $0 \le y \le y_i$ and

$$ |x - x_i| \le \frac{y_i - y}{2} \quad (\text{narrow}), \qquad |x - x_i| \le y_i - y \quad (\text{wide}). $$

Every nail head glows in the dark. A nail stops being visible the moment it is covered by a hat hung later (lying on that hat’s boundary already counts as covered). Furthermore, if a mage tries to hammer a nail at a point that is already covered by some hanging hat (boundary included), that mage is expelled and both the nail and the hat are discarded — the hat is never hung.

After every mage acts, report how many glowing nail heads are visible.

The first line contains the number of test cases $Z$ ($1 \le Z \le 30$). The test cases follow one after another.

Each test case starts with a line containing an integer $n$ ($1 \le n \le 10^5$), the number of mages. Each of the next $n$ lines describes one mage, in the order they go to sleep, and contains two integers $x_i$ ($-10^9 \le x_i \le 10^9$) and $y_i$ ($1 \le y_i \le 10^9$) followed by a single letter: W for a wide hat or N for a narrow hat.

For each test case output $n$ lines. The $i$-th line must be FAIL if the $i$-th mage was expelled while hammering the nail. Otherwise it must contain a single integer: the number of glowing nail heads visible immediately after the $i$-th mage hangs their hat.