Xóa số

Xét dãy vô hạn các số tự nhiên liên tiếp bắt đầu từ \(1\): \(1, 2, 3,...\) và \(n\) số nguyên dương \(a_{1}, a_{2}, ..., a_{n}\). Trên dãy vô hạn các số tự nhiên này, tiến hành xóa hết các số chia hết cho \(a_{1}\), sau đó xóa hết các số chia hết cho \(a_{2}\) mà chưa được xóa,..., cuối cùng xóa hết các số chia hết cho \(a_{n}\) mà chưa được xóa. Đánh số các số chưa được xóa bắt đầu từ \(1\), người ta muốn biết số được đánh số thứ \(k\) là số nào?

Yêu cầu: Cho dãy số \(a_{1}, a_{2}, ..., a_{n}\) và \(k\), hãy tìm số tự nhiên được đánh số thứ \(k\) trên dãy sau khi xóa.

Input

--- Dòng đầu chứa số nguyên \(T\) là số bộ dữ liệu;

--- \(T\) nhóm dòng sau, mỗi nhóm có dạng:

o Dòng đầu của nhóm chứa hai số nguyên dương \(n\) và \(k\) \((1 ≤ k ≤ 10^{15})\);

o Dòng thứ hai của nhóm chứa \(n\) số nguyên dương \(a_{1}, a_{2}, ..., a_{n}\) \((1 < a_{i} ≤ 10^{15})\).

Output

• Gồm \(T\) dòng, mỗi dòng chứa một số tự nhiên là kết quả tương ứng của bộ test trong dữ liệu vào.

Example

1
2 5
3 4

10

Scoring

\(30\%\) số test có \(n = 1\)

\(30\%\) số test có \(n = 2\)

\(40\%\) số test có \(n \leq 10\)