Məsələlər
Co-prime
Co-prime
Given a number \textbf{N}, you are asked to count the number of integers between \textbf{A} and \textbf{B} inclusive which are relatively prime to \textbf{N}.
Two integers are said to be co-prime or relatively prime if they have no common positive divisors other than \textbf{1} or, equivalently, if their greatest common divisor is \textbf{1}. The number \textbf{1} is relatively prime to every integer.
\InputFile
The first line on input contains \textbf{T} (\textbf{0} < \textbf{T} ≤ \textbf{100}) the number of test cases, each of the next \textbf{T} lines contains three integers \textbf{A}, \textbf{B}, \textbf{N} where (\textbf{1} ≤ \textbf{A} ≤ \textbf{B} ≤ \textbf{10^15}) and (\textbf{1} ≤ \textbf{N} ≤ \textbf{10^9}).
\OutputFile
For each test case, print the number of integers between \textbf{A} and \textbf{B} inclusive which are relatively prime to \textbf{N}. Follow the output format below.
Giriş verilənləri #1
2 1 10 2 3 15 5
Çıxış verilənləri #1
Case #1: 5 Case #2: 10