#### Registered Users Only

Please login to utilize this feature.

Do note that this website only supports submissions in C++.

Problem #1: PokéPrime

PokéTrainer Little Joseph has been watching PokéMaster Ash and his journeys on the Television and is inspired to follow in his footsteps. After defeating Brock’s huge rock Pokémon with Little Joseph’s Squirtle shooting out small little bubbles, Little Joseph gets to Cerulean City.

Little Joseph enters Cerulean City Gym to fight Misty, but it seems that ever since Misty got on TV, there were too many PokéTrainers flocking from all over the Kanto region to see her. Hence, she has set up an annoying puzzle to stumble all the PokéTrainers.

We all know what primes are; they are numbers that can be divisible by ONLY 1 and themselves. But Misty has a challenge; Misty wants you to generate the x-th PokéPrime number (either Type A or Type B). There are two types of PokéPrime numbers: a Type A PokéPrime number is the prime number occupying prime-numbered positions (e.g. the 2nd prime number, the 3rd prime number, the 5th prime number…etc.) and a Type B PokéPrime number is the prime number occupying positive palindromic positions (e.g. the 1st prime number, the 2nd prime number … , the 9th prime number, the 11th prime number, the 22nd prime number etc.)

Your task as a PokéProgrammer is to help Little Joseph solve Misty’s puzzle so that Little Joseph can battle Misty for the gym badge.

Input

Misty will first throw to you an Unown character (A) or (B) followed by an integer x. 50% of the test cases will be an Unown character A and 50% of the test cases will be an Unown character B. The integer x will not exceed 150.

Output

A single line with an integer representing the x-th Type A or Type B PokéPrime number (depending on what Unown character Misty throws you).

Sample Input

A 8

Sample Output

67

Sample Input

B 11

Sample Output

79

PokéTrainer Little Joseph has been watching PokéMaster Ash and his journeys on the Television and is inspired to follow in his footsteps. After defeating Brock’s huge rock Pokémon with Little Joseph’s Squirtle shooting out small little bubbles, Little Joseph gets to Cerulean City.

Little Joseph enters Cerulean City Gym to fight Misty, but it seems that ever since Misty got on TV, there were too many PokéTrainers flocking from all over the Kanto region to see her. Hence, she has set up an annoying puzzle to stumble all the PokéTrainers.

We all know what primes are; they are numbers that can be divisible by ONLY 1 and themselves. But Misty has a challenge; Misty wants you to generate the x-th PokéPrime number (either Type A or Type B). There are two types of PokéPrime numbers: a Type A PokéPrime number is the prime number occupying prime-numbered positions (e.g. the 2nd prime number, the 3rd prime number, the 5th prime number…etc.) and a Type B PokéPrime number is the prime number occupying positive palindromic positions (e.g. the 1st prime number, the 2nd prime number … , the 9th prime number, the 11th prime number, the 22nd prime number etc.)

Your task as a PokéProgrammer is to help Little Joseph solve Misty’s puzzle so that Little Joseph can battle Misty for the gym badge.

Input

Misty will first throw to you an Unown character (A) or (B) followed by an integer x. 50% of the test cases will be an Unown character A and 50% of the test cases will be an Unown character B. The integer x will not exceed 150.

Output

A single line with an integer representing the x-th Type A or Type B PokéPrime number (depending on what Unown character Misty throws you).

Sample Input

A 8

Sample Output

67

Sample Input

B 11

Sample Output

79

### Tags

### Subtasks and Limits

Subtask | Score | #TC | Time | Memory | Scoring |
---|---|---|---|---|---|

1 | 0 | 2 | 1s | 32MB | Average |

2 | 100 | 10 | 1s | 32MB | Average |

### Judge Compile Command

g++ ans.cpp -o pokeprime -Wall -static -O2 -lm -m64 -s -w -std=gnu++14 -fmax-errors=512