Cho 2 số nguyên ~N~ và ~K~ ~(1 \le N \le 2^{64}-1; 3 \le K \le 10~). Tìm số nguyên lớn nhất không vượt quá ~N~ và là tích của ~K~ số nguyên tố liên tiếp.

Input

• Dòng đầu là số nguyên ~T~ tương ứng với số bộ test (~1 \le T \le 15~)
• ~T~ dòng tiếp theo mỗi dòng là 1 cặp số ~(N, K)~ cách nhau 1 dấu cách

Output

• Gồm ~T~ dòng là kết quả của ~T~ bộ test tương ứng, nếu không tìm được số thoả mãn in ra ~-1~

Sample Input

2
100 4
110 3

Sample Output

-1
105