Architect Omar is responsible for furnishing the new apartments after completion of its construction. Omar has a set of living room furniture, a set of kitchen furniture, and a set of bedroom furniture, from different manufacturers.
In order to furnish an apartment, Omar needs a living room furniture, a kitchen furniture, and two bedroom furniture, regardless the manufacturer company.
You are given a list of furniture Omar owns, your task is to find the maximum number of apartments that can be furnished by Omar.
The first line contains an integer T (1 ≤ T ≤ 100), where T is the number of test cases.
The first line of each test case contains an integer n (1 ≤ n ≤ 1000), where n is the number of available furniture from all types. Then n lines follow, each line contains a string s representing the name of a furniture.
Each string s begins with the furniture's type, then followed by the manufacturer's name. The furniture's type can be:
All strings are non-empty consisting of lowercase and uppercase English letters, and digits. The length of each of these strings does not exceed 50 characters.
For each test case, print a single integer that represents the maximum number of apartments that can be furnished by Omar
## Input
The first line contains an integer T (1 ≤ T ≤ 100), where T is the number of test cases.The first line of each test case contains an integer n (1 ≤ n ≤ 1000), where n is the number of available furniture from all types. Then n lines follow, each line contains a string s representing the name of a furniture.Each string s begins with the furniture's type, then followed by the manufacturer's name. The furniture's type can be: _bed_, which means that the furniture's type is bedroom. _kitchen_, which means that the furniture's type is kitchen. _living_, which means that the furniture's type is living room. All strings are non-empty consisting of lowercase and uppercase English letters, and digits. The length of each of these strings does not exceed 50 characters.
## Output
For each test case, print a single integer that represents the maximum number of apartments that can be furnished by Omar
[samples]
**Definitions**
Let $ T \in \mathbb{Z} $ be the number of test cases.
For each test case $ k \in \{1, \dots, T\} $:
- Let $ n_k \in \mathbb{Z} $ be the number of furniture items.
- Let $ F_k = \{s_1, s_2, \dots, s_{n_k}\} $ be the multiset of furniture strings, where each string $ s_i $ begins with one of the prefixes: `"living"`, `"kitchen"`, or `"bedroom"`.
Define:
- $ L_k = $ count of strings in $ F_k $ starting with `"living"`.
- $ K_k = $ count of strings in $ F_k $ starting with `"kitchen"`.
- $ B_k = $ count of strings in $ F_k $ starting with `"bedroom"`.
**Constraints**
1. $ 1 \le T \le 100 $
2. For each $ k \in \{1, \dots, T\} $:
- $ 1 \le n_k \le 1000 $
- $ L_k, K_k, B_k \ge 0 $
**Objective**
For each test case $ k $, compute the maximum number of apartments that can be furnished, where each apartment requires:
- 1 living room furniture,
- 1 kitchen furniture,
- 2 bedroom furniture.
$$
\text{Answer}_k = \min\left(L_k, K_k, \left\lfloor \frac{B_k}{2} \right\rfloor\right)
$$