{"raw_statement":[{"iden":"statement","content":"John has to stay indoors for a whole month. He is overwhelmed with boredom and decides to purchase a pocket computer. After evaluating several offers, he chooses a Chinese one, as it is the cheapest. A few days later, the computer arrives and John is thrilled to discover that the device has an interesting gaming function.\n\nThe game consists of the computer randomly choosing *a positive number $<= 10^9$*. The player has to guess the number only by asking the computer several comparisons with a different number specified by the player which will be answered by the computer with $T r u e$ or $F a l s e$. After a while, John suspects that there must be some contradictions in the computer's answers, realising that some of the answers are wrong. John wants to know which is the smallest possible number of wrong answers given by the computer without knowing the initial number chosen by the computer.\n\nThe first line of the input will contain the number $T$, representing the number of test cases.\n\nThe first line of each test will contain one positive number $N$, the number of questions asked.\n\nThe next N lines will contain one character $C$, one integer $X$, $| X | <= 10^9$, and one string $S$. The character $C$ can be either $<$, $>$ or $=$ and $S$ is either $T r u e$ or $F a l s e$.\n\nIt is guaranteed that the sum of all questions is smaller than 10^6.\n\nThe output file should consist of $T$ lines, each line containing one integer, the minimum possible number of wrong answers.\n\nDue to the large amount of data in the output, it is recommended to use stream desynchronization, if you are going to write using standard streams in C++.\n\nIn the first test case, if the number the computer chose is 5, then all the questions are answered correctly, so the answer is 0 wrong answers.\n\nIn the second test case, both questions cannot be true at the same time, so then the minimum number of wrong answers is 1.\n\n"},{"iden":"input","content":"The first line of the input will contain the number $T$, representing the number of test cases.The first line of each test will contain one positive number $N$, the number of questions asked.The next N lines will contain one character $C$, one integer $X$, $| X | <= 10^9$, and one string $S$. The character $C$ can be either $<$, $>$ or $=$ and $S$ is either $T r u e$ or $F a l s e$.It is guaranteed that the sum of all questions is smaller than 10^6."},{"iden":"output","content":"The output file should consist of $T$ lines, each line containing one integer, the minimum possible number of wrong answers.Due to the large amount of data in the output, it is recommended to use stream desynchronization, if you are going to write using standard streams in C++."},{"iden":"note","content":"In the first test case, if the number the computer chose is 5, then all the questions are answered correctly, so the answer is 0 wrong answers.In the second test case, both questions cannot be true at the same time, so then the minimum number of wrong answers is 1."}],"translated_statement":null,"sample_group":[],"show_order":[],"formal_statement":"**Definitions**  \nLet $ n \\in \\mathbb{Z}^+ $ be the number of magical sources.  \nLet $ A = (a_1, a_2, \\dots, a_n) $ be a sequence of integers representing mana changes.\n\n**Constraints**  \n1. $ 1 \\leq n \\leq 500000 $  \n2. $ -10^9 \\leq a_i \\leq 10^9 $ for all $ i \\in \\{1, \\dots, n\\} $\n\n**Objective**  \nFind the minimal initial mana $ m_0 \\in \\mathbb{R} $ such that for all $ k \\in \\{1, \\dots, n\\} $, the cumulative mana after visiting the $ k $-th source is non-negative:  \n$$\nm_0 + \\sum_{i=1}^{k} a_i \\geq 0\n$$  \nEquivalently,  \n$$\nm_0 \\geq -\\min_{1 \\leq k \\leq n} \\left( \\sum_{i=1}^{k} a_i \\right)\n$$  \nThus, the minimal required initial mana is:  \n$$\nm_0 = \\max\\left(0, -\\min_{1 \\leq k \\leq n} S_k \\right), \\quad \\text{where } S_k = \\sum_{i=1}^{k} a_i\n$$","simple_statement":"What is the minimum starting mana needed so that after applying each mana change in order, the mana never goes negative?","has_page_source":false}