Qurban 2011#6068
Qurban is an Islamic practice that involves the sacrifice of certain livestock. Qurban is done only on the - Zulhijjah, which is the last month in the Islamic calendar. Livestock to be slaughtered (and sacrificed) are limited to camels, cattle, buffaloes, sheep or goats. The meat from each slaughtered camel, cattle, or buffalo can be divided into equal parts to be shared by persons. Since goats and sheep are small in size compared to the other livestock, therefore one goat or sheep is equivalent to one part of the previous three previous livestock. A person can register to sacrifice more than one part.
In order to get the correct number of livestock to be slaughtered, one has to ensure that all parts is accounted for in order to slaughter one buffalo. If not, there will be a cost liability to the person in charge. In a situation when a person registers for more than parts, for example parts of a buffalo, the remainder of one part has to be combined with parts sacrificed by other persons.
Normally, the buffaloes and sheep are supplied by farmer, and the location for slaughtering is done at different places depending on the customers. There is only one truck that can transport either the buffaloes or the sheep. The truck can transport a maximum of buffaloes or sheep at one time.
Given a list of orders for qurban, calculate the minimum number of trips to transport the buffaloes and sheep to be slaughtered.
The input consists of a few lines of data. The first line is an integer , which represents the number of test data. It is followed by lines of data. Each of these lines begins with an integer , which represents the number of order, followed by a single space and a set of orders. The orders are in the following format: two characters where the first is either character '' (represents parts of a buffalo) or '' (represents a sheep). This is followed by an integer that represents the number of orders for the respective parts of cow or sheep. Each order is separated by a single space.
The output is the minimum number of trips to transport the buffaloes and sheep to be slaughtered.
Example 1