Coprime Count in a Range

Given a natural number $N$, count how many integers between $A$ and $B$, inclusive, are coprime with $N$.

Two integers are coprime when the only positive integer that divides both of them is 1. In other words, they are coprime when their greatest common divisor is 1. The number 1 is coprime with every integer.

The first line contains the number of test cases $T$. ($0 < T \le 100$)

Each test case is one line holding three integers $A$, $B$, $N$ separated by spaces. ($1 \le A \le B \le 10^{15}$, $1 \le N \le 10^9$)

For each test case print one line in the form Case #x: y, where $x$ is the test case number starting from 1 and $y$ is how many integers between $A$ and $B$, inclusive, are coprime with $N$.

Among the numbers in $[1, 10]$, the ones coprime with 2 are $1, 3, 5, 7, 9$.