{"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\u003eTonight $$$n$$$ young men are going to participate in Peter\u0027s campfire party. They decide to play an ancient counting-out game which was first described by Titus Flavius Josephus. Here is a brief introduction to the game.\u003c/p\u003e\u003cp\u003eBefore starting the game, these young men will stand in a circle around the campfire and the first man to join the circle will start the game. Counting will begin at the first man and proceed around the circle in the counterclockwise direction repeatedly. That is, the first man will report one at the beginning, and the second one in the counterclockwise direction will report two, and so forth, until a poor man reports $$$k$$$ and consequently leaves the circle to become a bystander. The game will be repeated with the remaining men, restarting from the next man in the counterclockwise direction who will be the new first man, going in the same direction, until all the young men have left the circle.\u003c/p\u003e\u003cp\u003ePeter wanna be the $$$m$$$-th one who left the circle since he strongly believes this number is lucky for him. As a sophisticated programmer, can you point out the right place he should stand at before the game start so that he can achieve his goal?\u003c/p\u003e\u003cp\u003eFor the sake of clarity, we assume the index of the first man to join the circle is $$$1$$$, the index of the next man in his counterclockwise direction is $$$2$$$, and so on. By the definition, the index of the last man in that direction should be $$$n$$$, and your task is to determine the index of the place Peter wants.\u003c/p\u003e"}},{"title":"Input","value":{"format":"HTML","content":"\u003cp\u003eThe input contains several test cases, and the first line contains a positive integer $$$T$$$ indicating the number of test cases which is up to $$$1000$$$.\u003c/p\u003e\u003cp\u003eFor each test case, the only line contains three integers $$$n, m$$$ and $$$k$$$ where $$$1 \\le n, m, k \\le 10^{18}$$$ and $$$n \\ge m$$$.\u003c/p\u003e\u003cp\u003eWe guarantee that the sum of $$$\\min\\{m, k\\}$$$ (i.\u0026nbsp;e. the minimum of $$$m$$$ and $$$k$$$) in all test cases is no larger than $$$2 \\times 10^6$$$.\u003c/p\u003e"}},{"title":"Output","value":{"format":"HTML","content":"\u003cp\u003eFor each test case, output a line containing \"\u003cspan class\u003d\"tex-font-style-tt\"\u003eCase #x: y\u003c/span\u003e\" (without quotes), where \u003cspan class\u003d\"tex-font-style-tt\"\u003ex\u003c/span\u003e is the test case number starting from $$$1$$$, and \u003cspan class\u003d\"tex-font-style-tt\"\u003ey\u003c/span\u003e is the index of the right place.\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\u003e20\n10 1 2\n10 2 2\n10 3 2\n10 4 2\n10 5 2\n10 6 2\n10 7 2\n10 8 2\n10 9 2\n10 10 2\n10 1 3\n10 2 3\n10 3 3\n10 4 3\n10 5 3\n10 6 3\n10 7 3\n10 8 3\n10 9 3\n10 10 3\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003eCase #1: 2\nCase #2: 4\nCase #3: 6\nCase #4: 8\nCase #5: 10\nCase #6: 3\nCase #7: 7\nCase #8: 1\nCase #9: 9\nCase #10: 5\nCase #11: 3\nCase #12: 6\nCase #13: 9\nCase #14: 2\nCase #15: 7\nCase #16: 1\nCase #17: 8\nCase #18: 5\nCase #19: 10\nCase #20: 4\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\u003eThe sample cases indeed show the order of the young men to leave the circle when $$$(n, k)$$$ is set to $$$(10, 2)$$$ and $$$(10, 3)$$$ respectively.\u003c/p\u003e"}}]}