#!/usr/bin/ruby
require 'prime'
n=gets.to_i
a=[0,*[-1]*n]
Prime.each(n){|e|
	n.downto(e){|i|
		if a[i-e]>=0
			a[i]=[a[i-e]+1,a[i]].max
		end
	}
}
p a[n]