{"trustable":true,"sections":[{"title":"","value":{"format":"MD","content":"You are given a dataset consisting of $N$ items. Each item is a pair of a word and a boolean denoting whether the given word is a spam word or not.\r\n\r\nWe want to use this dataset for training our latest machine learning model. Thus we want to choose some subset of this dataset as training dataset. We want to make sure that there are no contradictions in our training set, i.e. there shouldn\u0027t be a word included in the training set that\u0027s marked both as spam and not-spam. For example item {\"fck\", 1}, and item {\"fck, 0\"} can\u0027t be present in the training set, because first item says the word \"fck\" is a spam, whereas the second item says it is not, which is a contradiction.\r\n\r\nYour task is to select the maximum number of items in the training set.\r\n\r\nNote that same pair of {word, bool} can appear multiple times in input. The training set can also contain the same pair multiple times.\r\n\r\n### Input\r\n- First line will contain $T$, number of test cases. Then the test cases follow.\r\n- The first line of each test case contains a single integer $N$.\r\n- $N$ lines follow. For each valid $i$, the $i$-th of these lines contains a string $w_i$, followed by a space and an integer(boolean) $s_i$, denoting the $i$-th item.\r\n\r\n### Output\r\nFor each test case, output an integer corresponding to the maximum number of items that can be included in the training set in a single line.\r\n\r\n### Constraints\r\n- $1 \\le T \\le 10$\r\n- $1 \\le N \\le 25,000$\r\n- $1 \\le |w_i| \\le 5$ for each valid $i$\r\n- $0 \\le s_i \\le 1$ for each valid $i$\r\n- $w_1, w_2, \\ldots, w_N$ contain only lowercase English letters\r\n\r\n### Example Input\r\n```\r\n3\r\n3\r\nabc 0\r\nabc 1\r\nefg 1\r\n7\r\nfck 1\r\nfck 0\r\nfck 1\r\nbody 0\r\nbody 0\r\nbody 0\r\nram 0\r\n5\r\nvv 1\r\nvv 0\r\nvv 0\r\nvv 1\r\nvv 1\r\n```\r\n\r\n### Example Output\r\n```\r\n2\r\n6\r\n3\r\n```\r\n\r\n### Explanation\r\n**Example case 1:** You can include either of the first and the second item, but not both. The third item can also be taken. This way the training set can contain at the very max 2 items.\r\n\r\n**Example case 2:** You can include all the items except the second item in the training set.\r\n"}}]}