Вася и Петя выписали на доску все натуральные числа от 1 до n и играют в игру (n может быть достаточно велико, но Васю и Петю это не смущает).
Игроки по очереди выбирают числа, начинает Вася. Если на данном ходу было выбрано число x, то в дальнейшем в игре нельзя выбирать само число x и все его остальные натуральные степени (x2, x3, ...). К примеру, если на первом ходу выбрано число 9, то в дальнейшем числа 9 и 81 выбирать нельзя, в то время как числа 3 и 27 выбрать разрешается. Проигрывает тот, кто не может сделать ход.
Кто выигрывает при оптимальной игре обоих соперников?
Выходные данные
Выведите имя победителя — «Vasya» или «Petya» (без кавычек).
Примечание
В первом примере Вася выберет 1 и сразу выиграет.
Во втором примере вне зависимости от первого хода Васи Петя сможет выбрать оставшееся число и победить.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
1
|
Vasya
|
|
2
|
2
|
Petya
|
|
3
|
8
|
Petya
|