Cho hai số \(n\) và \(k\), in ra thừa số nguyên tố thứ \(k\) trong phân tích thừa số nguyên tố của \(n\).

Dữ liệu vào

• Dòng đầu tiên chứa số nguyên \(T\) là số bộ dữ liệu vào kiểm tra, mỗi bộ dữ liệu vào gồm một dòng chứa hai số nguyên dương \(n, k\) cách nhau một dấu cách.

Ràng buộc:

• \(0 < T \leq 100; 0 < N \leq 10^5; 0 < k \leq 50.\)

Kết quả

• in ra \(T\) dòng, mỗi dòng in ra thừa số nguyên tố thứ \(k\) trong phân tích thừa số nguyên tố của \(n\). Nếu \(k\) lớn hơn số lượng các thừa số nguyên tố của \(n\) thì in ra -1.

Ví dụ:

INPUT

2
225 2
81 5

OUTPUT

3
-1

Giải thích:

• Test 1: \(n = 225\) và \(k = 2\), 225 = 3 x 3 x 5 x 5. Thừa số nguyên tố thứ 2 là 3.
• Test 2: \(n = 81\) và \(k = 5\), 81 = 3 x 3 x 3 x 3, vì \(k = 5\) lớn hơn số lượng các thừa số nguyên tố của 81, do đó ta in ra -1.