Нормальні числа

Обмеження: 2 сек., 256 МіБ

Петрик дуже любить різні числові послідовності з різними числовими властивостями. Коли йому стає нудно, він записує якісь довільні числа на аркуші паперу, а тоді шукає якісь цікавинки. А якшо не знаходить, то придумує:)

Записавши числову послідовність, Петрик почав чомусь рахувати для кожного числа скільки менших за нього різних простих чисел стоїть зліва від цього числа. Цю кількість Петрик назвав числом нормальності для числа.

Ваше завдання — допомогти Петрику порахувати числа нормальності для усіх чисел, які він записав на аркуші.

Вхідні дані

У першому рядку задано одне ціле число \(n\) — кількість чисел, записаних Петриком.

У другому рядку задано \(n\) цілих чисел \(a_i\) — Петрикова числовою послідовністю.

Вихідні дані

У єдиному рядку виведіть \(n\) цілих чисел — нормальності для всіх членів послідовності у відповідному порядку.

Обмеження

\(1 \le n, a_i \le 5 \cdot 10^5\).

Приклади