Hi all I am trying this problem using digit dp approach though I have not applied memoization yet but my recursive backtrack is not working appropriately . please help me to figure out where is the problem

Number         Binary          Adjacent Bits

     12                    1100                        1

     15                    1111                        3

     27                    11011                      2

#include<iostream>
#define ll long long 
using namespace std;
ll n;
ll x=0;
ll solve(ll index, ll small, ll last){
	if(index==x)
		return 0;
	ll ans=0;	
	if(small){
		ll ans1=solve(index+1,small,0);
		ll ans2=solve(index+1,small,1);
		if(last==1) ans2++;
		ans=ans1+ans2;
	}
	else{
		if((n&(1<<(x-index-1)))!=0){
			ll ans1=solve(index+1, 1, 0);
			ll ans2=solve(index+1, 0, 1);
			if(last==1) ans2++;
			ans=ans1+ans2;			
		}
		else{
			ans=solve(index+1, 0, 0);
		}		
	}
	return ans;
}
int main(){			
	ll t;
	cin>>t;
	while(t--){
				
		cin>>n;
		ll cpy	= n;
		x=0;
		while(cpy>0){
			x++;
			cpy/=2;
		}		
		cout<<solve(0,0,0)<<"\n";
	}
	return 0;
}