{"raw_statement":[{"iden":"problem statement","content":"Let $\\mathrm{popcount}(n)$ be the number of `1`s in the binary representation of $n$. For example, $\\mathrm{popcount}(3) = 2$, $\\mathrm{popcount}(7) = 3$, and $\\mathrm{popcount}(0) = 0$.\nLet $f(n)$ be the number of times the following operation will be done when we repeat it until $n$ becomes $0$: \"replace $n$ with the remainder when $n$ is divided by $\\mathrm{popcount}(n)$.\" (It can be proved that, under the constraints of this problem, $n$ always becomes $0$ after a finite number of operations.)\nFor example, when $n=7$, it becomes $0$ after two operations, as follows:\n\n*   $\\mathrm{popcount}(7)=3$, so we divide $7$ by $3$ and replace it with the remainder, $1$.\n*   $\\mathrm{popcount}(1)=1$, so we divide $1$ by $1$ and replace it with the remainder, $0$.\n\nYou are given an integer $X$ with $N$ digits in binary. For each integer $i$ such that $1 \\leq i \\leq N$, let $X_i$ be what $X$ becomes when the $i$\\-th bit from the top is inverted. Find $f(X_1), f(X_2), \\ldots, f(X_N)$."},{"iden":"constraints","content":"*   $1 \\leq N \\leq 2 \\times 10^5$\n*   $X$ is an integer with $N$ digits in binary, possibly with leading zeros."},{"iden":"input","content":"Input is given from Standard Input in the following format:\n\n$N$\n$X$"},{"iden":"sample input 1","content":"3\n011"},{"iden":"sample output 1","content":"2\n1\n1\n\n*   $X_1 = 7$, which will change as follows: $7 \\rightarrow 1 \\rightarrow 0$. Thus, $f(7) = 2$.\n*   $X_2 = 1$, which will change as follows: $1 \\rightarrow 0$. Thus, $f(1) = 1$.\n*   $X_3 = 2$, which will change as follows: $2 \\rightarrow 0$. Thus, $f(2) = 1$."},{"iden":"sample input 2","content":"23\n00110111001011011001110"},{"iden":"sample output 2","content":"2\n1\n2\n2\n1\n2\n2\n2\n2\n2\n2\n2\n2\n2\n2\n2\n2\n2\n2\n2\n2\n1\n3"}],"translated_statement":null,"sample_group":[],"show_order":["default"],"formal_statement":null,"simple_statement":null,"has_page_source":true}