Два числа называются взаимно простыми, если они не имеют общего натурального делителя, кроме 1. Иными словами, их наибольший общий делитель равен 1.

Найдите количество шестизначных чисел, взаимно простых с числом 70.

Var j, n : Longint;

Function Check (a, b : Longint) : Boolean;

Var i : Longint;

Begin

Check:=True;

For i:=2 to b do If ((a mod i) = 0) and ((b mod i) = 0) then Check:=False;

end;

Begin

n:=0;

For j:=100000 to 999999 do If Check (j, 70) then Inc (n) ;

Writeln (n) ;

end.