Buxoro ko'chasi

Masala tavsifi

Buxoroda yangi uzun ko‘cha qurilmoqda, undagi uylar $1$ dan boshlab natural sonlar bilan raqamlanadi: $1, 2, 3, 4, 5, \dots$.

Ammo shahar bosh me’mori ko‘chaga o‘ziga xos uslub berishga qaror qildi. Raqami $3$ ga yoki $5$ ga karrali bo‘lgan barcha uylar raqamlar bilan yozilmaydi — ularning o‘rnida fasadda dekorativ belgi qo‘yiladi. Qolgan uylar odatdagi raqamli lavhani oladi.

Agar yo‘lovchi ko‘radigan narsalarni ketma-ket yozsak, quyidagi ketma-ketlik hosil bo‘ladi: $1, 2, *, 4, *, *, 7, 8, *, *, 11, *, 13, 14, , 16, \dots$, bu yerda $\ast$ belgisi ga yoki ga karrali bo‘lgan uyni bildiradi.

Pochta tashuvchi faqat odatdagi raqamli lavhaga ega uylar bilan ishlaydi (ya’ni raqami $3$ ga ham, $5$ ga ham karrali bo‘lmagan uylar). U ko‘chadan chapdan o‘ngga qarab yurganida quyidagi ketma-ketlikni ko‘radi: $1, 2, 4, 7, 8, 11, 13, 14, 16, \dots$

Sizga $N$ soni beriladi ($1 \le N \le 10^9$). Odatdagi raqamli lavhaga ega uylardan $N$-chisi bo‘ladigan uyning raqamini toping.

Kirish formati

Yagona qatorda butun son $N$ beriladi.

Chiqish formati

Bitta butun sonni chiqar­ing — $3$ ga ham, $5$ ga ham karrali bo‘lmagan uylar orasida $N$-chi bo‘lgan uyning raqami.

Baholash tizimi

3

4

6

11