{"problem":{"name":"Anything Goes to Zero","description":{"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$. Let $f(n)$ be","description_type":"Markdown"},"platform":"AtCoder","limit":{"time_limit":2000,"memory_limit":262144},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"aising2020_d"},"statements":[{"statement_type":"Markdown","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)$.\n\n## Constraints\n\n*   $1 \\leq N \\leq 2 \\times 10^5$\n*   $X$ is an integer with $N$ digits in binary, possibly with leading zeros.\n\n## Input\n\nInput is given from Standard Input in the following format:\n\n$N$\n$X$\n\n[samples]","is_translate":false,"language":"English"}],"meta":{"iden":"aising2020_d","tags":[],"sample_group":[["3\n011","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$."],["23\n00110111001011011001110","2\n1\n2\n2\n1\n2\n2\n2\n2\n2\n2\n2\n2\n2\n2\n2\n2\n2\n2\n2\n2\n1\n3"]],"created_at":"2026-03-03 11:01:14"}}