K. Goddbach conjecture
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

Goldbach's conjecture states that any even number greater than 2 can be written as the sum of two prime numbers. For example:

4 =2 +2
6 =3 +3
8 =3 +5
...
Instead, Ada Byron's setters propose Goddbach's conjecture: "any odd number greater than 1, which is not prime, can be described as the sum of two prime numbers. ". The first odd numbers greater than 1, which are not prime are: 9, 15, 21, ... and:
9 =2 +7
15 =2 +13
21 =2 +19
...
Unfortunately, Goddbach conjecture does not hold, and 27 is the first odd number that, not being prime, cannot be expressed as the sum of two prime numbers. But what can be done is to elaborate the Goddbach sequence, $$$\mathcal{G}$$$, with all the odd numbers that are not prime and can be written as the sum of two prime numbers. In this series, $$$\mathcal{G}_1=9$$$, $$$\mathcal{G}_2=15$$$, $$$\mathcal{G}_3=21$$$, ...

Given an index $$$i$$$, you are asked to compute the number at that position in $$$\mathcal{G}$$$, the Goddbach sequence, $$$\mathcal{G}_i$$$.

Input

There will be several test cases, represented by a number $$$C$$$ given in the first line of the input. Each test case consists of exactly one line, each of which contains a single index $$$i$$$, counted from position 1.

  • $$$1 \leq C \leq 500.000$$$
  • $$$1 \leq i \leq 500.000$$$
Output

The output should consist of as many lines as there are test cases defined in the input, $$$C$$$, so that each line should show the number of the Goddbach sequence occupying the position specified in the corresponding test case.

Example
Input
3
1
3
103
Output
9
21
759