Rightmost non-zero Digit in N!

<p><style type="text/css"></style></p> <p align="LEFT" style="margin-top: 0.08in; widows: 2; orphans: 2" class="western"></p> <p><span style="font-size: large;"><span style="font-family: Arial;"> </span></span></p> <p align="LEFT" style="margin-top: 0.08in; widows: 2; orphans: 2" class="western"></p> <p><span style="font-size: large;"> <p align="LEFT" style="margin-top: 0.08in; widows: 2; orphans: 2" class="western"><span style="font-family: Arial;">The expression N!, read as &quot;N factorial,&quot; denotes the product of the first N positive integers, where N is nonnegative. So, for example</span></p> <span style="font-family: Arial;"> </span></span><span style="font-family: Arial;"> <p align="LEFT" style="margin-top: 0.08in; widows: 2; orphans: 2" class="western"></p> </span><span style="font-size: large;"><span style="font-family: Arial;"> </span></span></p> <p></p> <p align="LEFT" style="margin-top: 0.08in; widows: 2; orphans: 2" class="western"></p> <p><span style="font-size: large;"><span style="font-family: Arial;"> </span></span></p> <p align="LEFT" style="margin-top: 0.08in; widows: 2; orphans: 2" class="western"></p> <p><span style="font-size: large;"> <p align="LEFT" style="margin-top: 0.08in; widows: 2; orphans: 2" class="western"><span style="font-family: Arial;">N N!</span></p> <span style="font-family: Arial;"> </span></span><span style="font-family: Arial;"> <p align="LEFT" style="margin-top: 0.08in; widows: 2; orphans: 2" class="western"></p> </span><span style="font-size: large;"><span style="font-family: Arial;"> </span></span></p> <p></p> <p align="LEFT" style="margin-top: 0.08in; widows: 2; orphans: 2" class="western"></p> <p><span style="font-size: large;"><span style="font-family: Arial;"> </span></span></p> <p align="LEFT" style="margin-top: 0.08in; widows: 2; orphans: 2" class="western"></p> <p><span style="font-size: large;"> <p align="LEFT" style="margin-top: 0.08in; widows: 2; orphans: 2" class="western"><span style="font-family: Arial;">0 1</span></p> <span style="font-family: Arial;"> </span></span><span style="font-family: Arial;"> <p align="LEFT" style="margin-top: 0.08in; widows: 2; orphans: 2" class="western"></p> </span><span style="font-size: large;"><span style="font-family: Arial;"> </span></span></p> <p></p> <p align="LEFT" style="margin-top: 0.08in; widows: 2; orphans: 2" class="western"></p> <p><span style="font-size: large;"><span style="font-family: Arial;"> </span></span></p> <p align="LEFT" style="margin-top: 0.08in; widows: 2; orphans: 2" class="western"></p> <p><span style="font-size: large;"> <p align="LEFT" style="margin-top: 0.08in; widows: 2; orphans: 2" class="western"><span style="font-family: Arial;">1 1</span></p> <span style="font-family: Arial;"> </span></span><span style="font-family: Arial;"> <p align="LEFT" style="margin-top: 0.08in; widows: 2; orphans: 2" class="western"></p> </span><span style="font-size: large;"><span style="font-family: Arial;"> </span></span></p> <p></p> <p align="LEFT" style="margin-top: 0.08in; widows: 2; orphans: 2" class="western"></p> <p><span style="font-size: large;"><span style="font-family: Arial;"> </span></span></p> <p align="LEFT" style="margin-top: 0.08in; widows: 2; orphans: 2" class="western"></p> <p><span style="font-size: large;"> <p align="LEFT" style="margin-top: 0.08in; widows: 2; orphans: 2" class="western"><span style="font-family: Arial;">2 2</span></p> <span style="font-family: Arial;"> </span></span><span style="font-family: Arial;"> <p align="LEFT" style="margin-top: 0.08in; widows: 2; orphans: 2" class="western"></p> </span><span style="font-size: large;"><span style="font-family: Arial;"> </span></span></p> <p></p> <p align="LEFT" style="margin-top: 0.08in; widows: 2; orphans: 2" class="western"></p> <p><span style="font-size: large;"><span style="font-family: Arial;"> </span></span></p> <p align="LEFT" style="margin-top: 0.08in; widows: 2; orphans: 2" class="western"></p> <p><span style="font-size: large;"> <p align="LEFT" style="margin-top: 0.08in; widows: 2; orphans: 2" class="western"><span style="font-family: Arial;">3 6</span></p> <span style="font-family: Arial;"> </span></span><span style="font-family: Arial;"> <p align="LEFT" style="margin-top: 0.08in; widows: 2; orphans: 2" class="western"></p> </span><span style="font-size: large;"><span style="font-family: Arial;"> </span></span></p> <p></p> <p align="LEFT" style="margin-top: 0.08in; widows: 2; orphans: 2" class="western"></p> <p><span style="font-size: large;"><span style="font-family: Arial;"> </span></span></p> <p align="LEFT" style="margin-top: 0.08in; widows: 2; orphans: 2" class="western"></p> <p><span style="font-size: large;"> <p align="LEFT" style="margin-top: 0.08in; widows: 2; orphans: 2" class="western"><span style="font-family: Arial;">4 24</span></p> <span style="font-family: Arial;"> </span></span><span style="font-family: Arial;"> <p align="LEFT" style="margin-top: 0.08in; widows: 2; orphans: 2" class="western"></p> </span><span style="font-size: large;"><span style="font-family: Arial;"> </span></span></p> <p></p> <p align="LEFT" style="margin-top: 0.08in; widows: 2; orphans: 2" class="western"></p> <p><span style="font-size: large;"><span style="font-family: Arial;"> </span></span></p> <p align="LEFT" style="margin-top: 0.08in; widows: 2; orphans: 2" class="western"></p> <p><span style="font-size: large;"> <p align="LEFT" style="margin-top: 0.08in; widows: 2; orphans: 2" class="western"><span style="font-family: Arial;">5 120</span></p> <span style="font-family: Arial;"> </span></span><span style="font-family: Arial;"> <p align="LEFT" style="margin-top: 0.08in; widows: 2; orphans: 2" class="western"></p> </span><span style="font-size: large;"><span style="font-family: Arial;"> </span></span></p> <p></p> <p align="LEFT" style="margin-top: 0.08in; widows: 2; orphans: 2" class="western"></p> <p><span style="font-size: large;"><span style="font-family: Arial;"> </span></span></p> <p align="LEFT" style="margin-top: 0.08in; widows: 2; orphans: 2" class="western"></p> <p><span style="font-size: large;"><span style="font-family: Arial;"> <p align="LEFT" style="margin-top: 0.08in; widows: 2; orphans: 2" class="western"><span style="font-size: large;"><font color="#000000">10 3628800 </font></span></p> </span></span><span style="font-size: large;"><span style="font-family: Arial;"> <p align="LEFT" style="margin-top: 0.08in; widows: 2; orphans: 2" class="western"></p> </span></span><span style="font-family: Arial;"> <p align="LEFT" style="margin-top: 0.08in; widows: 2; orphans: 2" class="western"></p> </span><span style="font-size: large;"><span style="font-family: Arial;"> </span></span></p> <p></p> <p align="LEFT" style="margin-top: 0.08in; widows: 2; orphans: 2" class="western"></p> <p><span style="font-size: large;"><span style="font-family: Arial;"> </span></span></p> <p align="LEFT" style="margin-top: 0.08in; widows: 2; orphans: 2" class="western"></p> <p><span style="font-size: large;"><span style="font-family: Arial;"> </span></span><span style="font-size: large;"><span style="font-family: Arial;"> <p align="LEFT" style="margin-top: 0.08in; widows: 2; orphans: 2" class="western"></p> </span></span><span style="font-family: Arial;"><span style="font-size: large;"> <p align="LEFT" style="margin-top: 0.08in; widows: 2; orphans: 2" class="western"></p> </span></span><span style="font-size: large;"><span style="font-family: Arial;"> <p align="LEFT" style="margin-top: 0.08in; widows: 2; orphans: 2" class="western"><font color="#000000">For this problem, you are to write a program that can compute the rightmost non-zero digit of the factorial for N in base B.</font></p> </span></span><span style="font-family: Arial;"> <p align="LEFT" style="margin-top: 0.08in; widows: 2; orphans: 2" class="western"></p> </span><span style="font-size: large;"><span style="font-family: Arial;"> <br /> </span></span></p> <p></p> <p></p>

<p><style type="text/css"></style></p> <p align="LEFT" style="margin-bottom: 0in; line-height: 0.23in; widows: 2; orphans: 2" class="western"><span style="font-size: large;"><span style="font-family: Arial;"> In the first line there is an integer T (T &lt;= 100), indicates the number of test cases.</span></span></p> <p align="LEFT" style="margin-bottom: 0in; line-height: 0.23in; widows: 2; orphans: 2" class="western"><span style="font-size: large;"><span style="font-family: Arial;"> <font color="#000000">In each case, there</font><font color="#000000"> is a</font> single line with integers N and B </span></span></p> <p align="LEFT" style="margin-bottom: 0in; line-height: 0.23in; widows: 2; orphans: 2" class="western"><span style="font-size: large;"><span style="font-family: Arial;"> (0&lt;=N&lt;=10^7, 2&lt;=B&lt;=10^4).</span></span></p> <p><span style="font-size: large;"><span style="font-family: Arial;"> <br /> </span></span></p> <p></p>

<p><style type="text/css"></style></p> <p align="LEFT" style="margin-bottom: 0in; line-height: 0.23in; widows: 2; orphans: 2" class="western"><span style="font-size: large;"><span style="font-family: Arial;"> For each case, the output format is &ldquo;Case #c: ans&rdquo;.&nbsp;</span></span></p> <p align="LEFT" style="margin-bottom: 0in; line-height: 0.23in; widows: 2; orphans: 2" class="western"><span style="font-size: large;"><span style="font-family: Arial;"> c is the case number start from 1.</span></span></p> <p align="LEFT" style="margin-bottom: 0in; line-height: 0.23in; widows: 2; orphans: 2" class="western"><span style="font-size: large;"><span style="font-family: Arial;"> ans is the answer of this problem. The ans is in base 10.</span></span></p> <p align="LEFT" style="margin-bottom: 0in; line-height: 0.23in; widows: 2; orphans: 2" class="western"><span style="font-size: large;"><span style="font-family: Arial;"> See the sample for more details. </span></span></p> <p><span style="font-size: large;"><span style="font-family: Arial;"> <br /> </span></span></p> <p></p>