Language: C++

#include <iostream> // cout, endl, cin
#include <string> // string, to_string, stoi
#include <vector> // vector
#include <algorithm> // min, max, swap, sort, reverse, lower_bound, upper_bound
#include <utility> // pair, make_pair
#include <tuple> // tuple, make_tuple
#include <cstdint> // int64_t, int*_t
#include <cstdio> // printf
#include <map> // map
#include <queue> // queue, priority_queue
#include <set> // set
#include <stack> // stack
#include <deque> // deque
#include <unordered_map> // unordered_map
#include <unordered_set> // unordered_set
#include <bitset> // bitset
#include <cctype> // isupper, islower, isdigit, toupper, tolower
#include<cmath>
#include<limits>
#define ll long long
#define ALL(x) (x).begin(),(x).end()
#define rep(i, n) for(int i = 0; i < (int)(n); i++)
#define int_INF 2147483647
#define pint_INF 2000000000
#define ll_INF 	9223372036854775807
#define MOD 1000000007
#define vi vector<int>
#define vvi vector<vector<int>>
#define vvll vector<vector<long long>>
#define vvc vector<vector<char>>
#define vll vector<long long>
#define pii pair<int,int>
#define vpii vector<pair<int,int>>
#define sysp system("PAUSE")
#define pno cout << "no" << endl
#define pyes cout << "yes" << endl
#define pYes cout << "Yes" << endl
#define pNo cout << "No" << endl
using namespace std;
const int M = 1000;
#define int ll
ll mpow(ll x, ll n, ll mod) { //x^n(mod M) ←普通にpow(x,n)では溢れてしまうため，随時mod計算
	ll ans = 1;
	while (n != 0) {
		if (n & 1) ans = ans * x % mod;
		x = x * x % mod;
		n = n >> 1;
	}
	return ans;
}

int ctoi(char c) {
	return c - '0';
}

template<typename T>
T original_pow(T a, T b,T base) {
	T ans = 1;
	rep(i, b) {
		ans *= a;
		ans %= base;
	}

	return  ans;
}
class Pop{
private:
	vector<int> SmallerMaxN;
	bitset<20> bs;
public:
	Pop() {
		SmallerMaxN.resize(M);
		SmallerMaxN[1] = 1;
		for (int i = 1; i < M; i++) {
			SmallerMaxN[i] = calc(i);
		}
		//SmallerMaxN[0] = 1;
	}

	int calc(int x) {
		if (x == 0) return 1;
		if (SmallerMaxN[x] != 0) {
			return SmallerMaxN[x];
		}
		else {
			bs = x;
			int y = x % bs.count();

			if (SmallerMaxN[y] != 0) {
				SmallerMaxN[x] =  SmallerMaxN[y] + 1;
				return SmallerMaxN[x];
			}
			else if(y == 0){
				return 1;
			}
			else {
				SmallerMaxN[y] = calc(y) + 1;
			}
		}

	}

	int LargeInput(string s) {
		int base = 0;
		for (int i = 0; i < s.size(); i++) {
			if (s[i] == '1') base++;
		}

		ll res = 0;
		for (int i = 0; i < s.size(); i++) {
			//res += ctoi(s[i]) * mpow(2, i, base);
			//int delta = ctoi(s[i]) * mpow(2, s.size()  - 1 -i, base);
			res += ctoi(s[i]) * original_pow(ll(2), s.size() - 1- i,base);
			//cout << ctoi(s[i]) << ":" << original_pow(ll(2), s.size() - 1 - i, base) << endl;
		}

		res %= base;
		return res;
	}

	void solve(string raw) {
		for (int i = 0; i < raw.size(); i++) {
			string temp = raw;
			if (temp[i] == '1') temp[i] = '0';
			else if (temp[i] == '0') temp[i] = '1';

			int Processed = LargeInput(temp);
			cout << SmallerMaxN[Processed] + 1 << endl;
		}
	}
};

void test(string s) {
	s = "1100101";
	ll ans = 0;
	for (int i = 0; i < s.size(); i++) {
		ans += ctoi(s[i]) * pow(2, s.size() - 1- i);
	}
	cout << ans << endl;
}
signed main() {
	Pop pp;
	int N; cin >> N;
	string s; cin >> s;
	pp.solve(s);
}
/*

*/

Compiler output:
a.cc: In member function 'long long int Pop::LargeInput(std::string)':
a.cc:20:12: error: expected primary-expression before 'long'
   20 | #define ll long long
      |            ^~~~
a.cc:113:58: note: in expansion of macro 'll'
  113 |                         res += ctoi(s[i]) * original_pow(ll(2), s.size() - 1- i,base);
      |                                                          ^~
a.cc: In member function 'long long int Pop::calc(long long int)':
a.cc:97:48: warning: control reaches end of non-void function [-Wreturn-type]
   97 |                                 SmallerMaxN[y] = calc(y) + 1;