@abhi2402 's answer completes everything. I would just add some more bits and parts to what I did and try to explain my solution-

### The Constraints:

1\le L,R\le10^9 make it obvious that the good old NLogN solution of iterating through all elements, then checking their binary form wont work .

However, the constraint that the groups must be of equal size is interesting. Lets say, that my current size of bits is K. Say I am debating on keeping size of each group p (where p \le K always). We can easily see that if p is not a multiple of K, then the grouping is not possible. also, for a particular group size p, we can have only 1 bit string for that K (Leading 0's not allowed!). This is a informal proof that going by “counting good pairs” is the way to go.

### The Preprocessing:

Since the max size of group is only 31 (as 2^{31}>10^9) I went the lazy way. For all group sizes i, I iterated through all numbers from 1 to i-1. Lets call them j. If I observe that j divides i, i.e. i\%j==0, then this is a valid size. I make the binary string of this size, and then convert it to decimal. Lets call this value A. I make a map and increment mp[A] by 1.

**Code-**

##
Click to view

```
string s="";
char ch='1';
for(i=1;i<=31;i++)
{
for(j=i;j>0;--j)
{
if(i%j==0)
{
k=1;
s="";
ch='1';
while(k<=i)
{
s+=ch;
if(k%j==0)ch=('1'+'0')-ch;
++k;
}
int a=toInt(s);
//cout<<s<<"===>"<<a<<" i="<<i<<" j="<<j<<endl;
mp[a]++;
}
}
}
```

### The Answering:

Recall the map which must have seemed highly redundant to you by now. . I made a map because, now, at this step, I can prefix sum entries of map like normal array.

**Code for prefix sum-**

##
Click to view

```
for(;l!=mp.end();++l,++m)//l=mp.begin()+1,m=l-1 , i.e. previous index
{
(*l).second+=(*m).second;
}
```

Its all the same. If my entry of map is, say (4,1) where 4 represents the key/index and 1 represents the value at that index, and the next value is (10,1), then after prefix sum it will be [(4,1),(10,2)].

Dont worry if you dont know maps, the basic principle is, I did prefix sum so that mp[A] denotes number of such good numbers which are \le A. This allows us to answer queries in O(1) by mp[R]-mp[L-1] , i.e. Number of good numbers in [L,R] = Number of good numbers \le R - Number of good Numbers \le L-1

Now, for every query, I find the nearest entry of map which I filled, adjust endpoints. If after adjusting, they were A and B, then my answer was simply mp[B]-mp[A-1].

**Code-**

##
Click to view

```
while(t--)
{
int l,r;
cin>>l>>r;
auto a=mp.lower_bound(l);
--a;
auto b=mp.upper_bound(r);
--b;
cout<<(*b).second-(*a).second<<endl;
}
```

(PS: I have not explained the map part in detail - I just stressed on the basic principle. I believe its you who should decide best how you want to implement the principle.).