Uva 11246

#include<bits/stdc++.h>
using namespace std;

#define ll long long int

const int N = 1000000000;

bool mark[N+1];

int main(){
    #ifdef ERFANUL007
        clock_t tStart = clock();
        freopen("input.txt", "r", stdin);
        freopen("output.txt", "w", stdout);
    #endif

    int t; cin >> t;

    while(t--){
        int n, k;
        cin >> n >> k;

        for(int i=1; i<=n; i++) mark[i] = 1;

        for(int i=1; i<=n/k; i++){
            if(mark[i]) mark[i*k] = 0;
        }
        int ans = 0;
        for(int i=1; i<=n; i++){
            if(mark[i]) ans++;
        }
        cout << ans << '\n';

        for(int i=1; i<=n; i++) mark[i] = 0;
    }

    #ifdef ERFANUL007
        fprintf(stderr, ">>> Runtime : %.9f\n", (double)(clock() - tStart)/CLOCKS_PER_SEC);
    #endif

    return 0;
}