{"trustable":true,"prependHtml":"\u003cscript\u003e\n window.katexOptions \u003d {\n delimiters: [\n {left: \u0027\\\\(\u0027, right: \u0027\\\\)\u0027, display: false},\n ]\n };\n\u003c/script\u003e\n","sections":[{"title":"","value":{"format":"HTML","content":"\u003cp\u003e\nDefine \u003cem\u003eS[n]\u003c/em\u003e as the number of subsets of {1, 2, ..., \u003cem\u003en\u003c/em\u003e} that contain no consecutive integers. For each \u003cem\u003eS[n]\u003c/em\u003e, if for all \u003cem\u003ei\u003c/em\u003e (1 ≤ \u003cem\u003ei\u003c/em\u003e \u0026lt; \u003cem\u003en\u003c/em\u003e) gcd(\u003cem\u003eS[i]\u003c/em\u003e, \u003cem\u003eS[n]\u003c/em\u003e) is 1, we call that \u003cem\u003eS[n]\u003c/em\u003e as a \u003cem\u003ePrime S\u003c/em\u003e. Additionally, \u003cem\u003eS[1]\u003c/em\u003e is also a \u003cem\u003ePrime S\u003c/em\u003e. For the \u003cem\u003eK\u003csup\u003eth\u003c/sup\u003e\u003c/em\u003e minimum \u003cem\u003ePrime S\u003c/em\u003e, we\u0027d like to find the minimum \u003cem\u003eS[n]\u003c/em\u003e which is multiple of \u003cem\u003eX\u003c/em\u003e and not less than the \u003cem\u003eK\u003csup\u003eth\u003c/sup\u003e\u003c/em\u003e minimum \u003cem\u003ePrime S\u003c/em\u003e. Please tell us the corresponding (\u003cem\u003eS[n]\u003c/em\u003e ÷ \u003cem\u003eX\u003c/em\u003e) mod \u003cem\u003eM\u003c/em\u003e.\n\u003c/p\u003e\n\u003ch4\u003eInput\u003c/h4\u003e\n\u003cp\u003e\nThere are multiple test cases. The first line of input is an integer T indicating the number of test cases.\n\u003c/p\u003e\n\u003cp\u003e\nFor each test case, there are 3 integers \u003cem\u003eK\u003c/em\u003e (1 ≤ \u003cem\u003eK\u003c/em\u003e ≤ 10\u003csup\u003e6\u003c/sup\u003e), \u003cem\u003eX\u003c/em\u003e (3 ≤ \u003cem\u003eX\u003c/em\u003e ≤ 100) and \u003cem\u003eM\u003c/em\u003e (10 ≤ \u003cem\u003eM\u003c/em\u003e ≤ 10\u003csup\u003e6\u003c/sup\u003e), which are defined in above description.\n\u003c/p\u003e\n\u003ch4\u003eOutput\u003c/h4\u003e\n\u003cp\u003e\nFor each test case, please output the corresponding (\u003cem\u003eS[n]\u003c/em\u003e ÷ \u003cem\u003eX\u003c/em\u003e) mod \u003cem\u003eM\u003c/em\u003e.\n\u003c/p\u003e\n\u003ch4\u003eSample\u003c/h4\u003e\n\u003ctable class\u003d\"vjudge_sample\"\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\u003e1\n1 3 10\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e1\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n\n"}}]}