Qurban 2011

Qurban is an Islamic practice of sacrificing livestock. It happens only from the 10th to the 13th of Zulhijjah, the last month of the Islamic calendar, and the animals allowed are camels, cattle, buffaloes, sheep, and goats.

For a camel, a cow, or a buffalo, the meat of one animal is split into 7 equal parts that 7 people share. A sheep or a goat is smaller than those three animals, so one of them counts as a single part. One person can register for two or more parts.

Slaughtering one buffalo requires all 7 of its parts to be taken. If they are not, the person in charge pays for the parts nobody took. When someone registers more than 7 parts, say 8 parts of a buffalo, the leftover part is combined with the parts other people registered. So the buffalo parts in one test data are added together, and the number of buffaloes to slaughter is that sum divided by 7 and rounded up.

The farmer supplies the buffaloes and the sheep, and the slaughtering place differs by customer. Only one truck is available for transport, and a single trip carries at most 3 buffaloes or at most 6 sheep. Buffaloes and sheep are never loaded on the same trip.

Given a list of qurban orders, find the minimum number of trips needed to transport every buffalo and sheep to be slaughtered.

The first line contains the number of test data $T$.

Each of the next $T$ lines starts with $m$, the number of orders on that line, then a single space, then the $m$ orders separated by single spaces. An order is a character and an integer written together. The character is b for parts of a buffalo or s for sheep, and the integer that follows is how many parts that order registers.

For each test data, print the minimum number of trips on its own line.