11977 - Story of Tomisu Ghost

n! (n階乘) 以 b 進制的數字系統表示時，最後面最少有 t 個零。本題給定 n 與 t，請你計算 b 最大可能的值為何。

Input

輸入資料的第一列有一個整數T( <= 4000)，表示測試資料的組數。每組資料有兩個整數 n (1 < n <= 100000)，t (0 < t <= 1000)，n與t皆以十進制表示(base 10)。

Output

請針對每組測試資料輸出資料編號與最大可能的 b 值，由於 b 可能非常大，故請取 b 除10000019的餘數。若無法找到任一個 b 值，請輸出 -1。

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

---

原文出處