### Problem

Given a number N, you are asked to count the number of integers between A and B inclusive which are relatively prime to N.
Two integers are said to be co-prime or relatively prime if they have no common positive divisors other than 1 or, equivalently, if their greatest common divisor is 1. The number 1 is relatively prime to every integer.

### Code

```#include <bits/stdc++.h>
using namespace std;
using ll = long long;

ll A, B, N;
vector<ll> po;

void calcpo() {
po.clear();
for(ll i = 2; i * i <= N; ++i) {
if(N && N % i == 0) {
po.push_back(i);
while(N && N % i == 0)
N /= i;
}
if(N == 1) break;
}
if(N > 1) po.push_back(N);
}

ll solve(ll n) {
ll ans = 0;
for(ll S = 1; S < (1LL << po.size()); ++S) {
ll val = 1, cnt = 0;
for(ll i = 0; i < po.size(); ++i) {
if(S & (1LL << i)) {
++cnt;
val *= po[i];
}
}
if(cnt & 1) ans += n / val;
else ans -= n / val;
}
return ans;
}

int main() {
int T, kase = 0; scanf("%d", &T);
while(T--) {
scanf("%lld%lld%lld", &A, &B, &N);
calcpo();
printf("Case #%d: %lld\n", ++kase, (B-solve(B)) - (A-1-solve(A-1)));
}
return 0;
}
```