Giải bài trực tuyến

Cho 2 số nguyên N và K (1 <= N <= 2⁶⁴ - 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