Vasya and Petya wrote down all integers from 1 to n to play the "powers" game (n can be quite large; however, Vasya and Petya are not confused by this fact).

Players choose numbers in turn (Vasya chooses first). If some number x is chosen at the current turn, it is forbidden to choose x or all of its other positive integer powers (that is, x^2, x^3, ...) at the next turns. For instance, if the number 9 is chosen at the first turn, one cannot choose 9 or 81 later, while it is still allowed to choose 3 or 27. The one who cannot make a move loses.

Who wins if both Vasya and Petya play optimally?


-----Input-----

Input contains single integer n (1 ≤ n ≤ 10^9).


-----Output-----

Print the name of the winner — "Vasya" or "Petya" (without quotes).


-----Examples-----
Input
1

Output
Vasya

Input
2

Output
Petya

Input
8

Output
Petya



-----Note-----

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.

Source: codeforces | Difficulty: HARD
Tags: Dynamic programming

Game theory


Solutions:
from sys import stdin, stdout
import math, collections
mod = 10 ** 9 + 7

def isPower(n):
	if n <= 1:
		return True
	for x in range(2, int(math.sqrt(n)) + 1):
		p = x
		while p <= n:
			p = p * x
			if p == n:
				return True
	return False
n = int(input())
arr = [0, 1, 2, 1, 4, 3, 2, 1, 5, 6, 2, 1, 8, 7, 5, 9, 8, 7, 3, 4, 7, 4, 2, 1, 10, 9, 3, 6, 11, 12]
ans = arr[int(math.log(n, 2))]
s = int(math.log(n, 2))
for i in range(3, int(n ** 0.5) + 1):
	if not isPower(i):
		ans ^= arr[int(math.log(n, i))]
		s += int(math.log(n, i))
ans ^= (n - s) % 2
print('Vasya' if ans else 'Petya')