Game with Powers

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 ², x ³, …) 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⁹).

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.

Solution:

#include <iostream>
#include <iomanip>
#include <stdio.h>
#include <set>
#include <vector>
#include <map>
#include <cmath>
#include <algorithm>
#include <memory.h>
#include <string>
#include <sstream>

using namespace std;

const int g[30] = {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};

bool was[66666];

int main() {
int n;
cin >> n;
int ans = 0;
int tot = n;
for (int u=2;u*u<=n;u++) was[u] = false;
  for (int u=2;u*u<=n;u++) {
    if (was[u]) continue;
    was[u] = true;
    int x = u, y = 1;
    while ((long long)x*u <= n) {
      x *= u;
      if ((long long)x*x <= n) was[x] = true;
      y++;
    }
    ans ^= g[y];
    tot -= y;
  }
  if (tot & 1) ans ^= 1;
  if (ans > 0) cout << "Vasya" << endl;
  else cout << "Petya" << endl;
  return 0;
}