Cho 2 số nguyên N và K (1 <= N <= 264 - 1, 3 <= K <= 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 <= T <= 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ố thỏa mãn in ra -1
Example

Input:
2
100 4
110 3

Output:
-1
105