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.