Cho một số nguyên dương ~N~, hãy biểu diễn ~N~ dưới dạng tổng của các số nguyên tố sao cho số lượng số hạng trong tổng là lớn nhất có thể.

Input

• Số nguyên dương ~N~ trên 1 dòng

Constraints

~1 \le N \le 10^{12}~

Output Format

• Dòng 1. In ra số lượng số hạng trong tổng. Nếu không thể biểu diễn ~N~ dưới dạng tổng các số nguyên tố thì in ra -1.

Sample Input 0

6

Sample Output 0

3

Sample Input 1

1

Sample Output 1

-1