Cho ~2~ số nguyên ~N~ và ~K~ ~\left(1 \leq N \leq 2^{64} - 1;\text{ } 3 \leq K \leq 10\right)~. 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 ~\left(1 \leq T \leq 15\right)~.
• ~T~ dòng tiếp theo mỗi dòng là ~1~ cặp số ~\left(N, K\right)~ 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ố thỏa mãn in ra ~-1~.

Sample Input

2
100 4
110 3

Sample Output

-1
105