페리 선적 IV

다리가 흔하지 않던 시절에는 강 건너로 자동차를 실어 나르기 위해 페리를 사용했다. 강 페리는 더 큰 페리와 달리 안내선(가이드 라인)을 따라 움직이며 강물의 흐름으로 동력을 얻는다. 자동차는 페리의 한쪽 끝으로 올라타고, 페리가 강을 건너면 반대쪽 끝으로 내린다.

길이가 $l$미터인 페리가 강을 건넌다. 자동차는 양쪽 강기슭 중 어느 곳에나 도착하여 반대편 기슭으로 실려 갈 수 있다. 페리는 자동차를 싣고 있거나 어느 한쪽 기슭에 기다리는 자동차가 하나라도 있는 한, 두 기슭 사이를 쉬지 않고 왕복한다. 페리가 어느 기슭에 도착하면 싣고 있던 자동차를 모두 내린 뒤, 기다리고 있는 자동차들을 도착한 순서대로 갑판에 실을 수 있는 만큼 싣는다. 갑판에는 자동차를 한 줄로만 실을 수 있다. 페리는 처음에 왼쪽 기슭에 있었는데, 그곳에서 고장이 나 수리하는 데 꽤 오랜 시간이 걸렸다. 그동안 양쪽 기슭에는 강을 건너려는 자동차들이 줄지어 늘어섰다.

첫째 줄에 테스트 케이스의 수 $c$가 주어진다. 각 테스트 케이스는 두 정수 $l$과 $m$으로 시작한다. 이어지는 $m$개의 줄에는 자동차들이 도착하는 순서대로 정보가 주어진다. 각 줄에는 자동차의 길이(센티미터 단위)와 자동차가 도착한 기슭(left 또는 right)이 주어진다.

각 테스트 케이스마다, 기다리는 모든 자동차를 실어 나르기 위해 페리가 강을 건너야 하는 횟수를 한 줄에 출력한다.