import math											
def delit_vse(p):											
	b1 = 0											
	b = p % 2											
	if b > 0:											
		j =3											
		q = math.sqrt(p)//1								
		while j <= q:									
			b = p % j									
			if b == 0:									
				b1 = j									
				j = q+1								
				#print (j1)								
			j +=2										
	else:												
		b1= 2											
	return b1											
q = 0													
max_a2_1 = 0											
max_a2_2 = 0											
													
nhp = 0												
nhp1 = 0												
proct_col = 0											
p =   5												
P = p + 50000000											
while p <=P:											
	#print (p)											
	num = delit_vse(p)									
													
	t = p - 1											
	s = 0												
	while (t % 2 == 0):										
		t //= 2;										
		s += 1;										
	t1 = t//1											
	#y = math.log( p )//1									
	#print (t,s)											
	col_raund = 0										
	a2 = 10	# p-2										
	if a2  > p-2:											
		a2 = p-2										
	s2 = s-1											
	hp = 0											
	while hp == 0:										
		nhp1 += 1										
		hp = 0										
		col1 = 0										
		a1 = 2										
		while a1 <= a2:									
			#print (a1, t1, p)								
			t2 = (2**s2)*t1								
			x = pow(a1, t2, p)								
			#print (x, a1, p)								
			if x == 1 or x == p-1 :							
				col1 += 1								
				if x == p-1 :								
					hp = 1							
			else:										
				if max_a2_1 <  a1 :						
					max_a2_1 = a1						
				a1 = a2								
				hp = 1								
			a1 +=1									
													
													
		s2 = s2 - 1										
		col_raund  += 1									
		if s2 <  0 :										
			hp = 1									
													
	if max_a2_2 < col_raund :								
		max_a2_2 = col_raund 								
													
	#print (p, col1, a2)									
	if col1 == a2 - 1:										
		if num > 0:										
			print ("-not-a-", p, proct_col, a2, col1, num)			
		else:											
			#print ("-blok-a-",p, "-s-", s)		# очередное простое число
			proct_col += 1								
	else:												
		if num == 0:										
			print ("-not-obr-", p, proct_col, num)				
	p +=2												
	q +=1												
	if q > 100000:										
		print ("-perep-",p,proct_col, nhp1, nhp, max_a2_1, max_a2_2 )	
# количество простых на диапазоне
		q = 0											
print ("-N blok-", proct_col)