Дано натуральне число ~n~.

Знайдіть наступне за ним просте число.

Обмеження

• ~1 \le t \le 20~
• ~1 \le n \le 10^{12}~

Формат вхідних даних

У першому рядку є ціле число ~t~: кількість тестів.

Після цього кожен рядок має натуральне число ~n~.

Формат вихідних даних

Для кожного тесту виведіть наступне просте число після ~n~.

Приклад вхідних даних

5
1
2
3
42
1337

Приклад вихідних даних

2
3
5
43
1361