Avoid time limit of odd number of odd divisors

Question

The problem set was on a contest: Given a range [L, R], find the number of integers in that range which have an odd number of odd divisors. ​For example, 1 has only one divisor and it is odd, 9 has three divisors {1, 3, 9} and all of them are odd. Meanwhile, 18 has six divisors {1, 2, 3, 6, 9, 18} but three of them are odd. So 1, 9 and 18 have an odd number of odd divisors.

Input Input will start with a positive integer T (T ≤ 10​5​) denoting the number of test cases. Each test case will have two positive integers L, R (1 ≤ L ≤ R ≤ 10​18​)​, the range.

Output For each test case, the first line will be the case number in the format “Case t: x” without the quotes. Here t is the case number starting from 1 and x is the number of integers that fall in the range [L, R]​ and have an odd number of odd divisors.

Sample

Input   Output

3

1 3

5 10

10 15   


Case 1: 2

Case 2: 2

Case 3: 0

What I code:

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

int main()
{
    int T;
    cin>>T;

    for(int j=0; j<T; j++)
    {
        int m, nx;
        cin>>m>>nx;
        int finalCount = 0;

        for(int kk=m; kk<nx; kk++) // number
        {
            // Note that this loop runs till square root
            int oddCounter = 0;
            for (int i=1; i<=sqrt(kk); i++)
            {
                if (kk%i == 0)
                {
                    // If divisors are equal, print only one
                    if (kk/i == i)
                    {
                        if (kk & 1)
                            oddCounter++;
                    }
                    else // Otherwise print both
                    {
                        if (i & 1)
                            oddCounter++;
                        if ((kk/i) & 1)
                            oddCounter++;

                    }
                }
            }

            if ( oddCounter& 1)
                finalCount++;
        }

        cout<<"Case "<<j+1<<": "<<finalCount<<"\n";

    }

    //auto var_name = 0;
    //cout<<var_name<<"\n";

}

But got time limit exceeded.

CPU: 2s

Memory: 1500MB

How can I improve my code? Any suggestion?