Ferry Loading IV

Before bridges were common, ferries were used to carry cars across rivers. Unlike their larger cousins, river ferries run along a guide line and are powered by the river's current. Cars drive onto the ferry from one end, the ferry crosses the river, and the cars drive off from the other end.

A ferry $l$ meters long crosses the river. A car may arrive at either bank to be carried to the opposite side. The ferry moves continuously back and forth between the banks as long as it is carrying a car, or at least one car is waiting at either bank. Whenever the ferry reaches a bank it unloads whatever it is carrying and then loads the cars waiting to cross, taking them in the order they arrived and only as far as they fit on its deck. The deck holds a single lane of cars. The ferry starts on the left bank, where it broke down and took a long time to repair; while it was out of service, lines of cars formed on both banks waiting to cross the river.

The first line contains $c$, the number of test cases. Each test case begins with two integers $l$ and $m$. The next $m$ lines describe the cars in the order they arrive: each line gives the length of a car in centimeters and the bank at which it arrives, either left or right.

For each test case, print a single line containing the number of times the ferry must cross the river to serve all of the waiting cars.