Dit is een Lemming (of toch onze meest geslaagde poging tot een getrouwe weergave ervan):

Lemmings zijn zeer vastberaden wandelaars: ze stappen zonder te aarzelen in een rechte lijn tegen een constante snelheid vooruit. Als ze een hindernis tegenkomen, draaien ze zich ogenblikkelijk om en stappen voort in de tegenovergestelde richting. Bijvoorbeeld, beschouw de volgende kamer:

De kamer is 6m breed en de Lemming verplaatst zich tegen 1m/s.

Na 4 s botst de Lemming tegen de rechtermuur en keert hij zich om.
6 s later botst hij tegen de linkermuur. Hij keert zich weer om.
Om de 6 s blijft de Lemming tegen een muur botsen, tot in de oneindigheid.

De Lemming Liberation League vindt dit echter onaanvaardbaar en vraagt ons een deur te plaatsen:

Na 4 s botst de Lemming tegen de rechtermuur en keert hij zich om.
6 s later loopt de Lemming door de deur en verlaat hij de kamer.

Met andere woorden, de Lemming heeft na 10 s de kamer verlaten.
Maar wat gebeurt er indien we een tweede Lemming aan de kamer toevoegen?

Na 1 s botsen de Lemmings tegen elkaar. Beide keren om.
De linkerlemming loopt 3m terug en heeft na 3 s de kamer verlaten.
De rechterlemming loopt 3m naar rechts (3 s), keert om en loopt 6m naar links (6 s).

De linkerlemming zal dus 4 s lang in de kamer doorbrengen, de rechterlemming 10 s.
Het doel van deze opgave is om, gegeven een kamerbreedte en een aantal Lemmings, te berekenen hoe lang het duurt eer alle Lemmings de kamer hebben verlaten.
We nemen hierbij aan dat de deur de volledige linkermuur openlaat.
De exacte regels zijn als volgt:

De breedte van de kamer is een geheel aantal meters. De deur bevindt zich telkens links.
Elke Lemming begint op een positie met een gehele coördinaat.
Elke Lemming wandelt tegen exact 1m/s.
Lemmings botsen als ze zich op eenzelfde positie bevinden. Op dat moment keren ze zich ogenblikkelijk om en stappen ze in de tegenovergestelde richting verder. Botsingen kunnen op niet-gehele coördinaten plaatsvinden.

Invoer

De eerste regel bevat het aantal testgevallen. Per testgeval volgt

Een regel met een positief geheel getal B, de breedte van de kamer, waarbij 10 ≤ B ≤ 1 000 000 000.
Een regel met een positief geheel getalN, het aantal Lemmings, waarbij 1 ≤ B ≤ 100 000.
N regels met een positief geheel getal x_i meteen gevolgd door een letter r_i. x_i stelt de beginpositie voor van de i-de Lemming. Hierbij is 0 ≤ xi ≤ B. De letter r_i stelt de initiële wandelrichting: dit is ofwel L voor links, ofwel R voor rechts.

Voorbeeldinvoer:

Uitvoer

Per testgeval druk je één regel af bestaande uit twee gehele getallen gescheiden door 1 spatie.

Het eerste getal stelt de index voor van het testgeval. Het eerste testgeval heeft index 1.
De tijd waarop de laatste Lemming de kamer verlaat.

Voorbeelduitvoer:

1 10
2 120
3 160