Một số được gọi là đẹp nếu số đó được biểu diễn thành tích của 2 số nguyên tố.

Yêu cầu: Cho số nguyên dương \(n\). Tìm số đẹp lớn nhất không vượt quá \(n\).

Input

• Dòng đầu tiên chứa số nguyên \(T (1≤T≤10^5)\) là số bộ test.

• \(T\) dòng tiếp theo, mỗi dòng chứa một số nguyên dương \(n(6≤n≤10^6 ).\)

Output

• Gồm T dòng, Gồm một số nguyên là số đẹp lớn nhất không vượt quá \(n\) ứng với test tương ứng.

Ràng buộc:

• Subtask 1: có 30% số test đầu tiên \(T ≤ 10^3, N ≤ 5000 \)

• Subtask 2: có 30% số test tiếp theo \(𝑇 = 1. \)

• Subtask 3: có 40% số test cuối cùng \(1 ≤ T ≤ 10^5.\)

Sample Input

2
8
30

Sample Output

6
26