Problems

# Distinct Primes

# Distinct Primes

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.

#### Input

The first line contains the number of test cases **t**. Each of the next **t** lines contains one integer **n** (**n** ≤ **2** * `10`

).^{6}

#### Output

Output **t** lines, each containing the corresponding lucky number for that test case.

Input example #1

2 1 2

Output example #1

30 42