{"trustable":true,"prependHtml":"\u003cstyle type\u003d\"text/css\"\u003e\n #problem-body \u003e pre {\n display: block;\n padding: 9.5px;\n margin: 0 0 10px;\n font-size: 13px;\n line-height: 1.42857143;\n word-break: break-all;\n word-wrap: break-word;\n color: #333;\n background: rgba(255, 255, 255, 0.5);\n border: 1px solid #ccc;\n border-radius: 6px;\n }\n\u003c/style\u003e\n","sections":[{"title":"","value":{"format":"HTML","content":"\u003cdiv id\u003d\"problem-body\"\u003e\n\t\u003cp\u003eLenka likes to bake cakes since her childhood, when she has learned to bake from her mom. She soon became a cake expert able to bake chocolate cakes, apple pies, muffins, cookies, cheese cakes, tortes and many other cakes.\u003c/p\u003e\r\n\u003cp\u003eRecently, she has started her studies of math at Comenius University in Bratislava. In the first year she is taking combinatorics class. Today she is studying for the final exam. Since the brain needs a lot of sugar to study math, she has baked, just for herself, her favorite, very delicious, strawberry cake.\u003c/p\u003e\r\n\u003cp\u003eThe cake, still hot, is lying on an \u003cstrong\u003eN\u003c/strong\u003e×\u003cstrong\u003eM\u003c/strong\u003e inch sheet pan. Hungrily waiting for the cake to cool off Lenka came up with an interesting combinatorial question: How many different possibilities to cut the cake are there so that every connected piece consists of some number of 1×1 inch unit squares?\u003c/p\u003e\r\n\u003ch3\u003eProblem specification\u003c/h3\u003e\r\n\u003cp\u003eThe cake can be viewed as a grid consisting of \u003cstrong\u003eN\u003c/strong\u003e×\u003cstrong\u003eM\u003c/strong\u003e unit squares. We are allowed to cut the cake along the grid lines. As a result the cake splits into several connected pieces. (Two unit squares remain connected if they share a side which was not cut.) How many different ways are there to cut the cake? We consider two cuttings of the cake to be the same if the resulting connected pieces of both cuttings have the same shape and are at the same positions within the cake. In other words, we are only counting those cuttings where no cut leads between two unit squares that are in the same connected piece.\u003c/p\u003e\r\n\u003cp\u003eThe following picture ilustrates all the 12 different possible ways how to cut a 2×2 inch cake: \u003cimg src\u003d\"CDN_BASE_URL/8a89983f3981bf40eb8f3ce693c07d34?v\u003d1725463742\" alt\u003d\"12 possible ways of cutting a 2×2 cake\"\u003e\u003cbr\u003e Note that cutting, for example, as on following picture\u003cbr\u003e \u003cimg src\u003d\"CDN_BASE_URL/1a32cb5516821419a9e303604644db0c?v\u003d1725463742\" alt\u003d\"Not a good way of cutting\"\u003e\u003cbr\u003e is the same as not cutting at all.\u003c/p\u003e\r\n\u003ch3\u003eInput specification\u003c/h3\u003e\r\n\u003cp\u003eThe first line of the input file contains an integer \u003cstrong\u003eT\u003c/strong\u003e specifying the number of test cases. Each test case is preceded by a blank line.\u003c/p\u003e\r\n\u003cp\u003eEach test case consists of a single line with two positive integers \u003cstrong\u003eN\u003c/strong\u003e and \u003cstrong\u003eM\u003c/strong\u003e – dimensions of the cake.\u003c/p\u003e\r\n\u003ch3\u003eOutput specification\u003c/h3\u003e\r\n\u003cp\u003eFor each test case output a line with a single positive integer – the number of different possibilities how to cut the cake.\u003c/p\u003e\r\n\u003ch3\u003eExample\u003c/h3\u003e\r\n\u003cp\u003e\u003cstrong\u003eInput:\u003c/strong\u003e\u003c/p\u003e\r\n\u003cpre\u003e2\r\n\r\n1 2\r\n\r\n2 2\r\n\u003c/pre\u003e\r\n\u003cp\u003e\u003cstrong\u003eOutput:\u003c/strong\u003e\u003c/p\u003e\r\n\u003cpre\u003e2\r\n12\r\n\u003c/pre\u003e\r\n\u003cp\u003e\u003cstrong\u003eNote\u003c/strong\u003e\u003c/p\u003e\r\n\u003cp\u003eFor all the test cases, \u003cem\u003emin\u003c/em\u003e(\u003cstrong\u003eN\u003c/strong\u003e,\u003cstrong\u003eM\u003c/strong\u003e)\u0026lt;\u003d5, \u003cem\u003emax\u003c/em\u003e(\u003cstrong\u003eN\u003c/strong\u003e,\u003cstrong\u003eM\u003c/strong\u003e)\u0026lt;\u003d130.\u003c/p\u003e\n\u003c/div\u003e"}}]}