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