{"trustable":false,"sections":[{"title":"","value":{"format":"HTML","content":"\u003cstyle type\u003d\"text/css\"\u003e\r\n\u003c/style\u003e\r\n\u003cp\u003e\r\n\t\u003cspan style\u003d\"mso-bidi-font-size:\r\n18.0pt\"\u003e\u003co:p\u003e\u003c/o:p\u003e\u003c/span\u003e\u003c/p\u003e\r\n\u003cdiv class\u003d\"Section1\"\u003e\r\n\t\u003cp style\u003d\"text-align:justify\"\u003e\r\n\t\tThe \u003cspan data-scayt_word\u003d\"fibonacci\" data-scaytid\u003d\"1\"\u003efibonacci\u003c/span\u003e number is defined by the following recurrence:\u003c/p\u003e\r\n\t\u003cul type\u003d\"disc\"\u003e\r\n\t\t\u003cli class\u003d\"MsoNormal\" style\u003d\"mso-margin-top-alt:auto;mso-margin-bottom-alt:auto;\r\n text-align:justify;mso-list:l1 level1 lfo3;tab-stops:list .5in\"\u003e\r\n\t\t\t\u003cb\u003efib(0) \u003d 0 \u003co:p\u003e\u003c/o:p\u003e\u003c/b\u003e\u003c/li\u003e\r\n\t\t\u003cli class\u003d\"MsoNormal\" style\u003d\"mso-margin-top-alt:auto;mso-margin-bottom-alt:auto;\r\n text-align:justify;mso-list:l1 level1 lfo3;tab-stops:list .5in\"\u003e\r\n\t\t\t\u003cb\u003efib(1) \u003d 1 \u003co:p\u003e\u003c/o:p\u003e\u003c/b\u003e\u003c/li\u003e\r\n\t\t\u003cli class\u003d\"MsoNormal\" style\u003d\"mso-margin-top-alt:auto;mso-margin-bottom-alt:auto;\r\n text-align:justify;mso-list:l1 level1 lfo3;tab-stops:list .5in\"\u003e\r\n\t\t\t\u003cb\u003efib(n) \u003d fib(n-1)+fib(n-2)\u003c/b\u003e\u003c/li\u003e\r\n\t\u003c/ul\u003e\r\n\t\u003cp class\u003d\"MsoNormal\" style\u003d\"text-align:justify\"\u003e\r\n\t\tBut we\u0026#39;re not interested in the \u003cspan data-scayt_word\u003d\"fibonacci\" data-scaytid\u003d\"2\"\u003efibonacci\u003c/span\u003e numbers here. We would like to know how many calls does it take to evaluate the \u003cb\u003en\u003c/b\u003e \u003cspan data-scayt_word\u003d\"th\" data-scaytid\u003d\"6\"\u003eth\u003c/span\u003e \u003cspan data-scayt_word\u003d\"fibonacci\" data-scaytid\u003d\"4\"\u003efibonacci\u003c/span\u003e number if we follow the given recurrence. Since the numbers are going to be quite large, we\u0026#39;d like to make the job a bit easy for you. We\u0026#39;d only need the last digit of the number of calls, when this number is represented in base \u003cb\u003eb\u003c/b\u003e.(\u003cstrong\u003eCheck this carefully\u003c/strong\u003e)\u003c/p\u003e\r\n\t\u003ch3 style\u003d\"text-align:justify\"\u003e\r\n\t\t\u003cspan style\u003d\"font-size:18.0pt;mso-bidi-font-size:\r\n13.5pt\"\u003eInput\u003co:p\u003e\u003c/o:p\u003e\u003c/span\u003e\u003c/h3\u003e\r\n\t\u003cp style\u003d\"margin:0in;margin-bottom:.0001pt;text-align:justify\"\u003e\r\n\t\tInput consists of several test cases. For each test you\u0026#39;d be given two integers \u003cb\u003en (0 \u0026lt;\u003d n \u0026lt; 2\u003csup\u003e63\u003c/sup\u003e-1), b (0 \u0026lt; b \u0026lt;\u003d 10000)\u003c/b\u003e. Input is terminated by a test case where \u003cb\u003en\u003d0\u003c/b\u003e and \u003cb\u003eb\u003d0\u003c/b\u003e, you must not process this test case.\u003c/p\u003e\r\n\t\u003ch3 style\u003d\"text-align:justify\"\u003e\r\n\t\t\u003cspan style\u003d\"font-size:18.0pt;mso-bidi-font-size:\r\n13.5pt\"\u003eOutput\u003co:p\u003e\u003c/o:p\u003e\u003c/span\u003e\u003c/h3\u003e\r\n\t\u003cp style\u003d\"margin:0in;margin-bottom:.0001pt;text-align:justify\"\u003e\r\n\t\tFor each test case, print the test case number first. Then print \u003cb\u003en\u003c/b\u003e, \u003cb\u003eb\u003c/b\u003e and the last digit (in base \u003cb\u003eb\u003c/b\u003e) of the number of calls. There would be a single space in between the two numbers of a line. \u003ci\u003eNote that the last digit has to be represented in decimal number system.\u003c/i\u003e\u003c/p\u003e\r\n\t\u003ch3 style\u003d\"text-align:justify\"\u003e\r\n\t\t\u003cspan style\u003d\"font-size:18.0pt;mso-bidi-font-size:\r\n13.5pt\"\u003eSample Input\u003co:p\u003e\u003c/o:p\u003e\u003c/span\u003e\u003c/h3\u003e\r\n\t\u003cpre style\u003d\"text-align:justify\"\u003e\r\n\t\u003cspan style\u003d\"font-size:11.0pt;mso-bidi-font-size:\r\n10.0pt\"\u003e0 100\u003co:p\u003e\u003c/o:p\u003e\u003c/span\u003e\u003c/pre\u003e\r\n\t\u003cpre style\u003d\"text-align:justify\"\u003e\r\n\t\u003cspan style\u003d\"font-size:11.0pt;mso-bidi-font-size:10.0pt\"\u003e1 100\u003co:p\u003e\u003c/o:p\u003e\u003c/span\u003e\u003c/pre\u003e\r\n\t\u003cpre style\u003d\"text-align:justify\"\u003e\r\n\t\u003cspan style\u003d\"font-size:11.0pt;mso-bidi-font-size:\r\n10.0pt\"\u003e2 100\u003co:p\u003e\u003c/o:p\u003e\u003c/span\u003e\u003c/pre\u003e\r\n\t\u003cpre style\u003d\"text-align:justify\"\u003e\r\n\t\u003cspan style\u003d\"font-size:11.0pt;mso-bidi-font-size:10.0pt\"\u003e3 100\u003co:p\u003e\u003c/o:p\u003e\u003c/span\u003e\u003c/pre\u003e\r\n\t\u003cpre style\u003d\"text-align:justify\"\u003e\r\n\t\u003cspan style\u003d\"font-size:11.0pt;mso-bidi-font-size:\r\n10.0pt\"\u003e10 10\u003co:p\u003e\u003c/o:p\u003e\u003c/span\u003e\u003c/pre\u003e\r\n\t\u003cpre style\u003d\"text-align:justify\"\u003e\r\n\t\u003cspan style\u003d\"font-size:11.0pt;mso-bidi-font-size:10.0pt\"\u003e0 0\u003c/span\u003e\u003c/pre\u003e\r\n\t\u003ch3 style\u003d\"text-align:justify\"\u003e\r\n\t\t\u003cspan style\u003d\"font-size:18.0pt;mso-bidi-font-size:\r\n13.5pt\"\u003eSample Output\u003co:p\u003e\u003c/o:p\u003e\u003c/span\u003e\u003c/h3\u003e\r\n\t\u003cpre style\u003d\"text-align:justify\"\u003e\r\n\t\u003cspan style\u003d\"font-size:11.0pt;mso-bidi-font-size:\r\n10.0pt\"\u003eCase 1: 0 100 1\u003co:p\u003e\u003c/o:p\u003e\u003c/span\u003e\u003c/pre\u003e\r\n\t\u003cpre style\u003d\"text-align:justify\"\u003e\r\n\t\u003cspan style\u003d\"font-size:11.0pt;mso-bidi-font-size:10.0pt\"\u003eCase 2: 1 100 1\u003co:p\u003e\u003c/o:p\u003e\u003c/span\u003e\u003c/pre\u003e\r\n\t\u003cpre style\u003d\"text-align:justify\"\u003e\r\n\t\u003cspan style\u003d\"font-size:11.0pt;mso-bidi-font-size:\r\n10.0pt\"\u003eCase 3: 2 100 3\u003co:p\u003e\u003c/o:p\u003e\u003c/span\u003e\u003c/pre\u003e\r\n\t\u003cpre style\u003d\"text-align:justify\"\u003e\r\n\t\u003cspan style\u003d\"font-size:11.0pt;mso-bidi-font-size:10.0pt\"\u003eCase 4: 3 100 5\u003co:p\u003e\u003c/o:p\u003e\u003c/span\u003e\u003c/pre\u003e\r\n\t\u003cpre style\u003d\"text-align:justify\"\u003e\r\n\t\u003cspan style\u003d\"font-size:11.0pt;mso-bidi-font-size:\r\n10.0pt\"\u003eCase 5: 10 10 7\u003co:p\u003e\u003c/o:p\u003e\u003c/span\u003e\u003c/pre\u003e\r\n\t\u003cdiv align\u003d\"center\" class\u003d\"MsoNormal\" style\u003d\"text-align:center\"\u003e\r\n\t\t\u003chr align\u003d\"center\" size\u003d\"2\" width\u003d\"100%\" /\u003e\r\n\t\u003c/div\u003e\r\n\t\u003cp class\u003d\"MsoNormal\"\u003e\r\n\t\t\u0026nbsp;\u003c/p\u003e\r\n\u003c/div\u003e"}}]}