### brucewayne123's blog

By brucewayne123, history, 6 years ago, hi everyone! i was trying this problem HENRY:- Henry and Lost Ranges

Henry is a curious little boy. He likes to play around with numbers. One day, he defined a fun ction f for natural numbers such that: f(X) = largest prime factor of X , where X > 1 For example: f(2) = 2

f(3) = 3

f(75) = 5

Now, Henry selected two integers A and B ( A ≤ B ) and counted all numbers X between A and B (both inclusive) such that f(X) = K . He found out that there are N such numbers. After that Henry went for playing. When he returned home, he found out that he had forgotten the upper limit of range i.e. the integer B . However, he remembers all other numbers i.e. A , K and N .

Henry wants to find out B as soon as possible. Can you help him finding it ?

Note:

● If there are multiple possible values of B , output the least value out of those.

● It is assured that the input will be in such a way that final value of B will be within the range of long long int .

Input

First line of input contains T , the number of test cases. The only line of each test case contains three integers A , K and N .

Output

For each test case, output a single line containing the integer B .

Constraints

● 1 ≤ T ≤ 5

● 2 ≤ A ≤ 10 9

● 2 ≤ K ≤ 11 and K is a prime number

● 0 ≤ N ≤ 152319

Example

Input:

5 3 2 4

5 3 4

4 5 4

5 7 4

3 11 4

Output:

32

18

20

28

44

Explanation

In the first case, least value of B such that there are exactly 4 numbers having largest prime factor as 2 in range [3,B] will be 32 (the 4 numbers are 4, 8, 16, 32 ).

In the second case, least value of B such that there are exactly 4 numbers having largest prime factor as 3 in range [5,B] will be 18 (the 4 numbers are 6, 9, 12, 18 ).

In the third case, least value of B such that there are exactly 4 numbers having largest prime factor as 5 in range [4,B] will be 20 (the 4 numbers are 5, 10, 15, 20 ).

In the fourth case, least value of B such that there are exactly 4 numbers having largest prime factor as 7 in range [5,B] will be 28 (the 4 numbers are 7, 14, 21, 28 ).

In the fifth case, least value of B such that there are exactly 4 numbers having largest prime factor as 11 in range [3,B] will be 44 (the 4 numbers are 11, 22, 33, 44 ).

my solution:- http://pastebin.com/VccNHSwz since k is <= 11 hence we have primes 2,3,5,7,11 only.. for a particular k i need to check only the numbers formed with combinations of all prime numbers<=k for example.. if k=5 then 2^a*3^b*5^c where c>=1 and a>=0 and b>=0.. so i precomputed all such numbers for all k in <=100000000 then i applied lower_bound to find the least b i am getting wrong answer although i think i have handled overflows correctly! please someone help me understand my mistake! PS:- code is lengthy because but very easy to understand  Comments (14)
 » Auto comment: topic has been updated by brucewayne123 (previous revision, new revision, compare).
 » B can be of order 10^18 ! generating numbers till 100000000 , wont be sufficient i guess .
•  » » Well, it was sufficient as for 11, we can have at max 200000 numbers whose largest prime is 11. So for other primes it'd be even smaller.
•  » » i am generating numbers upto the range of LLONG_MAX so i guess it was sufficient
 » 6 years ago, # | ← Rev. 2 →   I think the upperbound of B is unsigned long long. I got WA with long long and ACed after changing it to unsigned.
•  » » can you please share your accepted code? we cannot submit now hence i cannot check my logic! thnaks :)
•  » » »
 » How to solve the triangle question ?
 » Did you consider the case N = 0 ? Ans is A for this case
•  » » yes i added it seperately in my code..
 » 6 years ago, # | ← Rev. 2 →   I implemented the solution in python to avoid overflow issues but it is not very neat.Here is my solution: http://ideone.com/YukrSo Let me know if anything is unclear. :)Can someone please share their solutions to the two geometry problems? Thanks!
•  » » If all the points are collinear, then only no such line will exist. other wise there will always be one such line.
•  » » » I did exactly this but I don't know why I kept getting wa. :(
•  » » actually i was facing problem in handling overflows in c++.. :D