← 返回 uber 的题目列表Reach End with Steps of 1 or Prime-Ending-in-3 Steps (DP)
类型：online_judge
Given a positive integer n, you start at position 0 and want to reach exactly position n. In one move you may:
Move forward by 1 step; or
Move forward by p steps, where p is a prime number whose decimal representation ends with digit 3 (e.g., 3, 13, 23, 43, ...).
Determine whether there exists a sequence of moves that reaches exactly n. Output true if possible, otherwise false.
Input
One integer n.
Output
Print true or false.
Constraints
1 <= n <= 1e5
Samples
Input:
1
Output:
true
Input:
2
Output:
true
Input:
4
Output:
true
Input:
11
Output:
true
Input:
12
Output:
true
Example
Input
1
Output
true