Lucky Numbers are those positive integers that have at least three distinct prime factors. For example and are the first two. You are given a positive integer , and was asked to find the -th lucky number.
The first line contains the number of test cases . Each of the next lines contains one integer .
Print lines, each containing the corresponding lucky number for that test case.