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

Limits: 2 sec., 256 MiB

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

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

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

Input

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

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

Output

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

Constraints

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

Samples