All Tracks Algorithms Searching Binary Search Problem

Amit and Prime Numbers
Tag(s):

Binary Search, Bitmask, Easy-Medium

Problem
Editorial
Analytics

Amit likes to play with prime numbers. He is also very careful about his health and goes to gym regularly. After hard work of two years, Amit is able to lift weights that are prime numbers but less than 50.

Yogesh, being his good friend, challenges him to find the k'th number whose at least one prime divisor is less than 50.

Input

First line contains a single integer t denoting the number of test cases.

Each of the next t lines contains a single integer k.

Output

For each testcase, print a single line containing required output.

It is guaranted that the answer is less than or equal to 10^18.

Constraints

1 <= t <= 5
1 <= k <= 5*10^17

10% score :
1 <= k <= 10

40% score :
1 <= k <= 10^5

100% score :
Original constraints

SAMPLE INPUT
2
1
2
SAMPLE OUTPUT
2
3
Time Limit: 2.0 sec(s) for each input file.
Memory Limit: 256 MB
Source Limit: 1024 KB
Marking Scheme: Marks are awarded when all the testcases pass.
Allowed Languages: C, C++, C++14, Clojure, C#, D, Erlang, F#, Go, Groovy, Haskell, Java, Java 8, JavaScript(Rhino), JavaScript(Node.js), Julia, Lisp, Lisp (SBCL), Lua, Objective-C, OCaml, Octave, Pascal, Perl, PHP, Python, Python 3, R(RScript), Racket, Ruby, Rust, Scala, Swift, Visual Basic, Kotlin

CODE EDITOR

Initializing Code Editor...
Your Rating:

Contributor

This Problem was Asked in

IIT Roorkee

Challenge Name

CodeBattle

Notifications
View All Notifications