## Arithmetic Derivative

Time Limit: 1 sec
Memory Limit: 756 MB
Attempts: 146
Accuracy: 0.68%
Author: Akashdeep Goel

One day, gvaibhav21 came across the concept of arithmetic derivatives. Arithmetic derivative of a number n is defined as f(n).

f(n) = 0, if n=1

f(n) = 1, if n is a prime number

f(n) = a*f(b)+b*f(a), if n=a*b for some a,b>1. (Product rule)

It can be proved that no matter how we choose our a or b for finding the arithmetic derivative of n, it will always come out to be the same.

Now adkroxx being good in maths, defines special numbers as the numbers which satisfy f(n)=2*n.

adkroxx challenges gvaibhav21 to find the kth special number. Since gvaibhav21 doesn't like math, help him find the required value.

Input:

The first line of input contains an integer t, the number of test cases.
Next t lines each contain a positive integer k.

Output:

For each test case, print the greatest integer less than or equal to the natural log of kth special number in a new line.

Sample Input:

2

1

4

Sample Output:

2

9

Sample Explanation:

f(16) = f(4)*4+4*f(4) = 4*4+4*4 = 32 = 2*16.

16 is the 1st number to satisfy the property of special numbers.

floor( ln(16) )=2

Constraints:

1<=t<=20

1<=k<=10^5

ID

SUBMITTED AT

STATUS

LANGUAGE

TIME

MEMORY USED

USER

TIME

STATUS

LANGUAGE

TIME

MEMORY USED

2 years ago

cpp

0.07 sec

64 KB

2 years ago

cpp

0.07 sec

64 KB

2 years ago

cpp

0.83 sec

58972 KB

2 years ago

cpp14

0.26 sec

1428 KB