Server Time: Fri Jul 19, 2019 6:09 am
Welcome ( logout
1340 - Story of Tomisu Ghost
  PDF (English) Statistics Forum
Time Limit: 2 second(s) Memory Limit: 32 MB

It is now 2150 AD and problem-setters are having a horrified time as the ghost of a problem-setter from the past, Mr. Tomisu, is frequently disturbing them. As always is the case in most common ghost stories, Mr. Tomisu has an unfulfilled dream: he had set 999 problems throughout his whole life but never had the leisure to set the 1000th problem. Being a ghost he cannot set problems now so he randomly asks problem-setters to complete one of his unfinished problems. One problem-setter tried to convince him saying that he should not regret as 999 is nowhere near 1024 (210) and he should not worry about power of 10 being an IT ghost. But the ghost slapped him hard after hearing this. So at last one problem setter decides to complete his problem:

"n! (factorial n) has at least t trailing zeroes in b based number system. Given the value of n and t, what is the maximum possible value of b?"

Input

Input starts with an integer T (≤ 4000), denoting the number of test cases.

Each case contains two integers n (1 < n ≤ 105) and t (0 < t ≤ 1000). Both n and t will be given in decimal (base 10).

Output

For each case, print the case number and the maximum possible value of b. Since b can be very large, so print b modulo 10000019. If such a base cannot be found then print -1 instead.

Sample Input

Output for Sample Input

4

1000 1000

1000 2

10 8

4 2

Case 1: -1

Case 2: 5227616

Case 3: 2

Case 4: 2

 

 


Problem Setter: Shahriar Manzoor
Special Thanks: Jane Alam Jan, Md. Towhidul Islam Talukder
Developed and Maintained by
JANE ALAM JAN
Copyright © 2012
LightOJ, Jane Alam Jan