Вася Петя хоёр $1$-ээс $n$ хүртэл бүх тоонууд бичжээ.

Тоглогчид ээлжилж нүүх ба Васягаас эхлэнэ. Нүүдэл бүрт нэг тоо сонгоно. Хэрвээ $x$ тоог сонгосон л бол үүнээс хойш $x$ тооны зэргүүдээс ($x$, $x^2$, $x^3$, ...) сонгож болохгүй.

Жишээ нь $9$-г эхний нүүдэлдээ сонгосон бол $9$, $81$ гэх мэт тоонуудыг дараа нь сонгож болохгүй. Гэхдээ $3$, $27$-г бол сонгож болно. Нүүдэлгүй болсон нь хожигдоно. Хэрвээ Вася Петя хоёр зөв тоглож чадвал хэн нь хожих вэ.

Оролт

Ганц бүхэл тоо $n$ ($1 ≤ n ≤ 10^9$)

Гаралт

Ялагчийн нэр буюу "Vasya", "Petya" хоёрын нэгийг хэвлэнэ.

In the first sample Vasya will choose 1 and win immediately.

In the second sample no matter which number Vasya chooses during his first turn, Petya can choose the remaining number and win.