{"trustable":true,"prependHtml":"\u003cstyle type\u003d\u0027text/css\u0027\u003e\n .input, .output {\n border: 1px solid #888888;\n }\n .output {\n margin-bottom: 1em;\n position: relative;\n top: -1px;\n }\n .output pre, .input pre {\n background-color: #EFEFEF;\n line-height: 1.25em;\n margin: 0;\n padding: 0.25em;\n }\n \u003c/style\u003e\n \u003clink rel\u003d\"stylesheet\" href\u003d\"//codeforces.org/s/96598/css/problem-statement.css\" type\u003d\"text/css\" /\u003e\u003cscript\u003e window.katexOptions \u003d { disable: true }; \u003c/script\u003e\n\u003cscript type\u003d\"text/x-mathjax-config\"\u003e\n MathJax.Hub.Config({\n tex2jax: {\n inlineMath: [[\u0027$$$\u0027,\u0027$$$\u0027], [\u0027$\u0027,\u0027$\u0027]],\n displayMath: [[\u0027$$$$$$\u0027,\u0027$$$$$$\u0027], [\u0027$$\u0027,\u0027$$\u0027]]\n }\n });\n\u003c/script\u003e\n\u003cscript type\u003d\"text/javascript\" async src\u003d\"https://mathjax.codeforces.org/MathJax.js?config\u003dTeX-AMS_HTML-full\"\u003e\u003c/script\u003e","sections":[{"title":"","value":{"format":"HTML","content":"\u003cp\u003eIn a car factory each car needs to go through \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003ek\u003c/i\u003e\u003c/span\u003e stages in order to be ready for sale, and each stage needs one day to be completed.\u003c/p\u003e\u003cp\u003eThe process in the factory goes as follows. On the first day a car enters the first stage. On the second day a car moves from the first stage to the second stage, and a new car enters the first stage. On the third day a car moves from the second stage to the third stage, a car moves from the first stage to the second stage, and a new car enters the first stage, and so on. After \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003ek\u003c/i\u003e\u003c/span\u003e days (i.e. \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003ek\u003c/i\u003e\u003c/span\u003e stages) the car will be ready for sale.\u003c/p\u003e\u003cp\u003eYour task is simple, given the number of stages for each car to be ready, and the number of cars to be manufactured. How many days are needed to finish manufacturing all the cars?\u003c/p\u003e"}},{"title":"Input","value":{"format":"HTML","content":"\u003cp\u003eThe first line of the input contains an integer T (1 \u003cspan class\u003d\"tex-span\"\u003e ≤ \u003c/span\u003e \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003eT\u003c/i\u003e\u003c/span\u003e \u003cspan class\u003d\"tex-span\"\u003e ≤ \u003c/span\u003e 1000), where T is the number of the test cases.\u003c/p\u003e\u003cp\u003eEach test case has one line that contains two integers \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003en\u003c/i\u003e\u003c/span\u003e and \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003ek\u003c/i\u003e\u003c/span\u003e (1 \u003cspan class\u003d\"tex-span\"\u003e ≤ \u003c/span\u003e \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003en\u003c/i\u003e\u003c/span\u003e, \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003ek\u003c/i\u003e\u003c/span\u003e \u003cspan class\u003d\"tex-span\"\u003e ≤ \u003c/span\u003e \u003cspan class\u003d\"tex-span\"\u003e10\u003csup class\u003d\"upper-index\"\u003e9\u003c/sup\u003e\u003c/span\u003e), the number of cars to be manufactured and the number of stages each car requires.\u003c/p\u003e"}},{"title":"Output","value":{"format":"HTML","content":"\u003cp\u003eFor each test case, print a single integer that represents the number of required days to manufacture all the cars.\u003c/p\u003e"}},{"title":"Examples","value":{"format":"HTML","content":"\u003ctable class\u003d\u0027vjudge_sample\u0027\u003e\n\u003cthead\u003e\n \u003ctr\u003e\n \u003cth\u003eInput\u003c/th\u003e\n \u003cth\u003eOutput\u003c/th\u003e\n \u003c/tr\u003e\n\u003c/thead\u003e\n\u003ctbody\u003e\n \u003ctr\u003e\n \u003ctd\u003e\u003cpre\u003e4\n1 1\n2 3\n4 3\n14526 78965\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e1\n4\n6\n93490\n\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n"}},{"title":"Note","value":{"format":"HTML","content":"\u003cp\u003eLet\u0027s solve the third case to show how the process goes in the factory: \u003c/p\u003e\u003cul\u003e\u003cli\u003e \u003cspan class\u003d\"tex-font-style-bf\"\u003eFirst day\u003c/span\u003e: The first car will enter the first stage.\u003c/li\u003e\u003cli\u003e \u003cspan class\u003d\"tex-font-style-bf\"\u003eSecond day\u003c/span\u003e: The first car will move to the second stage, and the second car will enter the first stage.\u003c/li\u003e\u003cli\u003e \u003cspan class\u003d\"tex-font-style-bf\"\u003eThird day\u003c/span\u003e: The first car will move to the third stage, the second car will move to the second stage, and the third car will enter the first stage. At the end of this day the first car will be ready for sale.\u003c/li\u003e\u003cli\u003e \u003cspan class\u003d\"tex-font-style-bf\"\u003eFourth day\u003c/span\u003e: The second car will move to the third stage, the third car will move to the second stage, and the fourth car will enter the first stage. At the end of this day the second car will be ready for sale.\u003c/li\u003e\u003cli\u003e \u003cspan class\u003d\"tex-font-style-bf\"\u003eFifth day\u003c/span\u003e: The third car will move to the third stage, and the fourth car will move to the second stage. At the end of this day the third car will be ready for sale.\u003c/li\u003e\u003cli\u003e \u003cspan class\u003d\"tex-font-style-bf\"\u003eSixth day\u003c/span\u003e: The fifth car will move to the third stage. At the end of this day the fourth car will be ready for sale.\u003c/li\u003e\u003c/ul\u003e"}}]}