Избегайте ограничения по времени нечетного числа нечетных делителей

Задача была на конкурсе:
Учитывая диапазон [L, R], найдите количество целых чисел в этом диапазоне, которые имеют нечетное количество нечетных делителей. Например, 1 имеет только один делитель, и он нечетный, 9 имеет три делителя {1, 3, 9}, и все они нечетные. Между тем, 18 имеет шесть делителей {1, 2, 3, 6, 9, 18}, но три из них странные. Таким образом, 1, 9 и 18 имеют нечетное количество нечетных делителей.

вход
Ввод начнется с положительного целого числа T (T ≤ 10 5), обозначающего количество тестовых случаев. Каждый тестовый пример будет иметь два натуральных числа L, R (1 ≤ L ≤ R ≤ 10 18), диапазон.

Выход
Для каждого теста первая строка будет номером дела в формате «Case t: x» без кавычек. Здесь t — это номер дела, начиная с 1, а x — это число целых чисел, попадающих в диапазон [L, R] и имеющих нечетное число нечетных делителей.

Образец

Input   Output

3

1 3

5 10

10 15Case 1: 2

Case 2: 2

Case 3: 0

Что я кодирую:

#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";

}

Но полученный срок превышен.

CPU: 2s

Memory: 1500MB

Как я могу улучшить свой код?
Любое предложение?