쿠르반 2011

쿠르반은 이슬람에서 가축을 희생으로 바치는 의례다. 이슬람력의 마지막 달인 줄히자 10일부터 13일까지만 진행하며, 희생 가축은 낙타, 소, 물소, 양, 염소로 한정된다.

낙타, 소, 물소는 한 마리에서 나오는 고기를 똑같은 7몫으로 갈라 7명이 나눠 가진다. 양과 염소는 앞의 세 가축보다 몸집이 작아서 한 마리가 앞 가축의 한 몫에 해당한다. 한 사람이 두 몫 이상을 신청할 수 있다.

물소 한 마리를 잡으려면 7몫이 모두 채워져야 한다. 채워지지 않으면 담당자가 남은 몫의 비용을 부담한다. 어떤 사람이 7몫을 넘겨서 신청하면, 예를 들어 물소 8몫을 신청하면 남는 1몫은 다른 사람이 신청한 몫과 합친다. 따라서 한 테스트 데이터에 들어 있는 물소 몫은 모두 더하고, 잡아야 하는 물소 수는 그 합을 7로 나눈 뒤 올림한 값이다.

물소와 양은 농장에서 공급하고 도축 장소는 손님에 따라 다르다. 운반에 쓸 수 있는 트럭은 한 대뿐이고, 한 번 운행할 때 물소는 최대 3마리, 양은 최대 6마리까지 싣는다. 한 번의 운행에 물소와 양을 섞어 싣지 않는다.

쿠르반 주문 목록이 주어질 때, 잡아야 하는 물소와 양을 모두 옮기는 데 필요한 최소 운행 횟수를 구하라.

첫 줄에 테스트 데이터의 개수 $T$가 주어진다.

이어지는 $T$개의 줄에는 각각 그 줄의 주문 개수 $m$이 먼저 오고, 공백 한 칸 뒤에 주문 $m$개가 공백 한 칸으로 구분되어 주어진다. 주문은 문자 하나와 정수 하나를 붙여 쓴 형태다. 문자가 b면 물소의 몫, s면 양이고, 뒤에 오는 정수는 그 주문이 신청한 몫의 수다.

테스트 데이터마다 최소 운행 횟수를 한 줄에 하나씩 출력한다.