Dãy số ~U~ được định nghĩa như sau:

• ~U_1 = 2~, ~U_2 = 4~.
• Với ~n \ge 3~: nếu ~n~ chia hết cho ~3~ thì ~U_n = U_{n-1} + 3~; nếu ~n~ chia ~3~ dư ~1~ thì ~U_n = U_{n-3} + 1~; nếu ~n~ chia ~3~ dư ~2~ thì ~U_n = U_{n-2} + 2~.

Yêu cầu: Cho ~k~, tính ~U_k~ và in ra các giá trị từ ~U_1~ đến ~U_k~.

Input

Đọc từ file văn bản DAYSO.INP một số nguyên ~k~ ~(2 \le k \le 100)~.

Output

Ghi ra file văn bản DAYSO.OUT:

• Dòng đầu ghi ~U_k~.
• Các dòng tiếp theo ghi ~k~ giá trị đầu tiên của dãy.

Example input 1

3

Example output 1

7
2 4 7