{"trustable":true,"prependHtml":"\u003cscript async src\u003d\"https://mathjax.codeforces.org/MathJax.js?config\u003dTeX-AMS-MML_HTMLorMML\" type\u003d\"text/javascript\" /\u003e\n\u003cscript\u003e\n window.katexOptions \u003d { disable: true };\n\u003c/script\u003e\n","sections":[{"title":"","value":{"format":"HTML","content":"\u003cdiv class\u003d\"panel_content\"\u003eLet’s consider a sequence $\\{f(n)\\}$ which satisfies following 2 conditions.\u003cbr\u003e\u003cbr\u003e1.$f(0) \u003d 0, f(1) \u003d 1$.\u003cbr\u003e2.$f(n)\u003dAf(n-1)+f(n-2)$,for any integer $n \u0026gt; 1$.\u003cbr\u003eHere A is a constant integer.\u003cbr\u003e\u003cbr\u003eGiven a prime $p$ and an integer $x(0\\leq x\\leq p)$ , your task is to calculate $|\\{n|L\\leq n\\leq R,f(n)\\ mod\\ p \u003d x\\}|$ , i.e. the number of indices $n$ between $L$ and $R$ such as $f(n)\\ mod\\ p \u003d x$ .\u003cbr\u003e\u003c/div\u003e"}},{"title":"Input","value":{"format":"HTML","content":"There are several test cases.\u003cbr\u003e\u003cbr\u003eThe first line of the input contains an integer $T(1\\leq T\\leq 120)$ , the number of test cases.\u003cbr\u003e\u003cbr\u003eEach of the next $T$ lines contains 5 integers, $A,p,x,L,R(0\\leq A \u0026lt; 10^9,2\u0026lt;p\u0026lt;10^9,0\\leq x \u0026lt; p,1\\leq L\\leq R \\leq 10^{18})$\u003cbr\u003e"}},{"title":"Output","value":{"format":"HTML","content":"Print $T$ lines, containing the answer to the problem."}},{"title":"Sample","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\u003e2\r\n1 5 0 1 5\r\n2 29 12 3 6\r\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e1\r\n2\r\n\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n"}}]}