{"raw_statement":[{"iden":"statement","content":"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.\n\nIn order to furnish an apartment, Omar needs a living room furniture, a kitchen furniture, and two bedroom furniture, regardless the manufacturer company.\n\nYou are given a list of furniture Omar owns, your task is to find the maximum number of apartments that can be furnished by Omar.\n\nThe first line contains an integer T (1 ≤ T ≤ 100), where T is the number of test cases.\n\nThe 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.\n\nEach string s begins with the furniture's type, then followed by the manufacturer's name. The furniture's type can be: \n\nAll 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.\n\nFor each test case, print a single integer that represents the maximum number of apartments that can be furnished by Omar\n\n"},{"iden":"input","content":"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."},{"iden":"output","content":"For each test case, print a single integer that represents the maximum number of apartments that can be furnished by Omar"}],"translated_statement":null,"sample_group":[],"show_order":[],"formal_statement":"**Definitions**  \nLet $ T \\in \\mathbb{Z} $ be the number of test cases.  \nFor each test case $ k \\in \\{1, \\dots, T\\} $:  \n- Let $ n_k \\in \\mathbb{Z} $ be the number of furniture items.  \n- 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\"`.  \n\nDefine:  \n- $ L_k = $ count of strings in $ F_k $ starting with `\"living\"`.  \n- $ K_k = $ count of strings in $ F_k $ starting with `\"kitchen\"`.  \n- $ B_k = $ count of strings in $ F_k $ starting with `\"bedroom\"`.  \n\n**Constraints**  \n1. $ 1 \\le T \\le 100 $  \n2. For each $ k \\in \\{1, \\dots, T\\} $:  \n   - $ 1 \\le n_k \\le 1000 $  \n   - $ L_k, K_k, B_k \\ge 0 $  \n\n**Objective**  \nFor each test case $ k $, compute the maximum number of apartments that can be furnished, where each apartment requires:  \n- 1 living room furniture,  \n- 1 kitchen furniture,  \n- 2 bedroom furniture.  \n\n$$  \n\\text{Answer}_k = \\min\\left(L_k, K_k, \\left\\lfloor \\frac{B_k}{2} \\right\\rfloor\\right)  \n$$","simple_statement":"Omar has furniture of three types: living room, kitchen, and bedroom.  \nTo furnish one apartment, he needs:  \n- 1 living room furniture  \n- 1 kitchen furniture  \n- 2 bedroom furniture  \n\nGiven a list of furniture items, count how many complete apartments he can furnish.  \nEach item’s type is given in its name (e.g., \"livingroom_abc\", \"kitchen_xyz\", \"bedroom_123\").  \n\nFind the maximum number of apartments possible.","has_page_source":false}