{"raw_statement":[{"iden":"statement","content":"The city of single direction consists of n blocks in a row, numbered from 1 to n from left to right. *All of them are populated by citizens*, and some of them has gas stations. People in each block will go to the nearest block that has a gas station. The distance between two blocks i and j is |i - j|, where |x| is the absolute value of x.\n\nThe government wants to move at most one station from its original block to another block. What is the maximum distance that a citizen has to cross to get to his/her nearest station, if the government operated in a way that minimizes this distance?\n\nThe first line of input contains a single integer T (1 ≤ T ≤ 1200), the number of test cases.\n\nThe first line of each test case contains a single integer n (1 ≤ n ≤ 105), the number of blocks in the city.\n\nThe second line contains a string s of n characters, each character is either ‘+’, which represents a block with one gas station, or ‘.’ which represents a normal block.\n\nIt is guaranteed that there’s at least one block that has a gas station.\n\nThe total sum of n overall test cases doesn't exceed 5 × 106.\n\nFor each test case, print the answer on a single line.\n\n"},{"iden":"input","content":"The first line of input contains a single integer T (1 ≤ T ≤ 1200), the number of test cases.The first line of each test case contains a single integer n (1 ≤ n ≤ 105), the number of blocks in the city.The second line contains a string s of n characters, each character is either ‘+’, which represents a block with one gas station, or ‘.’ which represents a normal block.It is guaranteed that there’s at least one block that has a gas station.The total sum of n overall test cases doesn't exceed 5 × 106."},{"iden":"output","content":"For each test case, print the answer on a single line."}],"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} $ denote the number of blocks.  \n- Let $ s_k \\in \\{+,\\ .\\}^{n_k} $ be a string representing the city, where $ s_k[i] = '+' $ if block $ i $ has a gas station, and $ s_k[i] = '.' $ otherwise.  \n- Let $ G_k = \\{ i \\in \\{1, \\dots, n_k\\} \\mid s_k[i] = '+' \\} $ be the set of blocks with gas stations.  \n\n**Constraints**  \n1. $ 1 \\le T \\le 1200 $  \n2. $ 1 \\le n_k \\le 10^5 $ for each $ k $  \n3. $ |G_k| \\ge 1 $ for each $ k $  \n4. $ \\sum_{k=1}^T n_k \\le 5 \\times 10^6 $  \n\n**Objective**  \nLet $ d(i) = \\min_{g \\in G_k} |i - g| $ be the distance from block $ i $ to its nearest gas station.  \nLet $ D_k = \\max_{i \\in \\{1, \\dots, n_k\\}} d(i) $ be the maximum distance any citizen must travel.  \n\nThe government may move **at most one** gas station from its current block to any other block (possibly empty), i.e., replace one element $ g \\in G_k $ with some $ g' \\in \\{1, \\dots, n_k\\} \\setminus G_k $, or leave $ G_k $ unchanged.  \n\nFind the **minimum possible value of $ D_k $** after such a move.","simple_statement":"You are given a row of n blocks, each either has a gas station ('+') or not ('.'). Every person goes to the nearest gas station. You can move at most one station to any other block (or leave it unchanged). Your goal is to minimize the maximum distance any person has to walk to reach their nearest station. What is that minimum possible maximum distance?","has_page_source":false}