Lex Luthor: “Man will kill GOD “.

Lex has finally decided to defeat his archenemy Superman. For this, he has been

experimenting with General Zod’s DNA. After weeks of hard work, he succeeded in his

malicious plot.

He unleashes a monstrous artificially bred creature known as Doomsday.

Superman and Batman join forces to fight him and are aided by Wonder Woman. They decide to

impale Doomsday with Kryptonite spear. However, Kryptonite piece needs to satisfy one

important condition.

The piece must have piercing power equivalent to number of prime factors of the factorial of the number of bone protrusions on the body of Doomsday.

Given the number of protrusions, find the power of Kryptonite piece required .

Input-

First line contains T- the number of test cases.

Thereafter , T lines follow .

Each line contains a number N – the number of protrusions on body of Doomsday .

Output-

For each test case , print value of number of prime factors of factorial of N.

Constraints :-
1<=T<=$25*10^5$

1<=N<= $10^7$

Problem setter : Shivam Garg