{"raw_statement":[{"iden":"statement","content":"Have you ever played Minesweeper? It’s a cute little game that originates from the 1960s, and has been written for many computing platforms in use today.\n\nThe game consists of a two dimensional grid, and there are two types of cells in it.\n\nA mined cell, and an empty cell, which contains a single digit that indicates how many adjacent cells contain mines. Eech cell has at most 8 adjacent cells. \n\nIn this version of the game, you are going to build a level with the following rules: \n\n \n\nFor instance, the following is 4 * 5 valid grid with 12 mines (which are represented by an '*' character) and the maximum number for the empty cells is M = 3 :\n\n* * * * 2\n\n* * * * 2\n\n3 * * 3 1 \n\nWe are interested in the maximum number of mines that a grid with those properties can contain, can you find the answer for us?\n\nThe first line contains a single integer T denoting the number of test cases.\n\nEach test case consists of one line which contains three space separated integers:\n\nThe number of the rows in the grid r. (2 ≤ r ≤ 6).\n\nThe number of the columns in the grid c. (2 ≤ c ≤ 6).\n\nThe maximum number that any empty cell can contain. (1 ≤ M ≤ 8).\n\nFor each test print one line containing one integer, the maximum number of mines that a grid can contain.\n\nThe grid in the statement is a valid grid for the first sample.\n\n"},{"iden":"input","content":"The first line contains a single integer T denoting the number of test cases.Each test case consists of one line which contains three space separated integers:The number of the rows in the grid r. (2 ≤ r ≤ 6).The number of the columns in the grid c. (2 ≤ c ≤ 6).The maximum number that any empty cell can contain. (1 ≤ M ≤ 8)."},{"iden":"output","content":"For each test print one line containing one integer, the maximum number of mines that a grid can contain."},{"iden":"note","content":"The grid in the statement is a valid grid for the first sample."}],"translated_statement":null,"sample_group":[],"show_order":[],"formal_statement":"**Definitions**  \nLet $ A \\in [0, 359] \\cap \\mathbb{Z} $ be the rotation angle (in degrees).  \nLet $ W, H \\in \\mathbb{Z}^+ $, $ W, H \\leq 10^9 $, be the width and height of the window.  \nLet $ N \\in \\mathbb{Z} $, $ 3 \\leq N \\leq 10^5 $, be the number of vertices.  \nLet $ P = \\{(x_i, y_i) \\in \\mathbb{Z}^2 \\mid 0 \\leq x_i, y_i \\leq 10^9, i \\in \\{1, \\dots, N\\} \\} $ be the input polygon.\n\n**Transformations**  \n1. **Rotation**: Rotate each point $ (x_i, y_i) $ counterclockwise by angle $ A $ degrees:  \n   $$\n   (x_i', y_i') = \\left( x_i \\cos \\theta - y_i \\sin \\theta,\\ x_i \\sin \\theta + y_i \\cos \\theta \\right), \\quad \\theta = \\frac{A \\pi}{180}\n   $$\n\n2. **Scaling and Translation**:  \n   Let $ x_{\\min} = \\min_i x_i' $, $ x_{\\max} = \\max_i x_i' $,  \n   $ y_{\\min} = \\min_i y_i' $, $ y_{\\max} = \\max_i y_i' $.  \n   Scale and translate to fit the window:  \n   $$\n   \\hat{x}_i = W \\cdot \\frac{x_i' - x_{\\min}}{x_{\\max} - x_{\\min}}, \\quad\n   \\hat{y}_i = H \\cdot \\frac{y_i' - y_{\\min}}{y_{\\max} - y_{\\min}}\n   $$\n\n**Objective**  \nOutput the transformed points $ (\\hat{x}_i, \\hat{y}_i) $ for $ i = 1, \\dots, N $, with absolute or relative error $ \\leq 10^{-6} $.","simple_statement":"Rotate a polygon by A degrees counterclockwise, then scale it to fit exactly inside a W×H window, so its bounding box touches all four sides. Output the new coordinates of each point.","has_page_source":false}