All submissions for this problem are available.### Read problem statements in [Hindi](http://www.codechef.com/download/translated/NOV19/hindi/HRDSEQ.pdf), [Bengali](http://www.codechef.com/download/translated/NOV19/bengali/HRDSEQ.pdf), [Mandarin Chinese](http://www.codechef.com/download/translated/NOV19/mandarin/HRDSEQ.pdf), [Russian](http://www.codechef.com/download/translated/NOV19/russian/HRDSEQ.pdf), and [Vietnamese](http://www.codechef.com/download/translated/NOV19/vietnamese/HRDSEQ.pdf) as well. Chef decided to write an infinite sequence. Initially, he wrote $0$, and then he started repeating the following process: - Look at the last element written so far (the $l$-th element if the sequence has length $l$ so far); let's denote it by $x$. - If $x$ does not occur anywhere earlier in the sequence, the next element in the sequence is $0$. - Otherwise, look at the previous occurrence of $x$ in the sequence, i.e. the $k$-th element, where $k \lt l$, this element is equal to $x$ and all elements between the $k+1$-th and $l-1$-th are different from $x$. The next element is $l-k$, i.e. the distance between the last two occurrences of $x$. The resulting sequence is $(0, 0, 1, 0, 2, 0, 2, 2, 1, \ldots)$: the second element is $0$ since $0$ occurs only once in the sequence $(0)$, the third element is $1$ since the distance between the two occurrences of $0$ in the sequence $(0, 0)$ is $1$, the fourth element is $0$ since $1$ occurs only once in the sequence $(0, 0, 1)$, and so on. Chef has given you a task to perform. Consider the $N$-th element of the sequence (denoted by $x$) and the first $N$ elements of the sequence. Find the number of occurrences of $x$ among these $N$ elements. ### Input - The first line of the input contains a single integer $T$ denoting the number of test cases. The description of $T$ test cases follows. - The first and only line of each test case contains a single integer $N$. ### Output For each test case, print a single line containing one integer ― the number of occurrences of the $N$-th element. ### Constraints - $1 \le T \le 128$ - $1 \le N \le 128$ ### Subtasks **Subtask #1 (30 points):** $1 \le N \le 16$ **Subtask #2 (70 points):** $1 \le N \le 128$ ### Example Input ``` 1 2 ``` ### Example Output ``` 2 ``` ### Explanation **Example case 1:** The $2$-nd element is $0$. It occurs twice among the first two elements, since the first two elements are both $0$.
|Tags||challenge, implementation, mynk322, nov19, watcher|
|Time Limit:||1 sec|
|Source Limit:||50000 Bytes|
|Languages:||C, CPP14, JAVA, PYTH, PYTH 3.6, PYPY, CS2, PAS fpc, PAS gpc, RUBY, PHP, GO, NODEJS, HASK, rust, SCALA, swift, D, PERL, FORT, WSPC, ADA, CAML, ICK, BF, ASM, CLPS, PRLG, ICON, SCM qobi, PIKE, ST, NICE, LUA, BASH, NEM, LISP sbcl, LISP clisp, SCM guile, JS, ERL, TCL, SQL, kotlin, PERL6, TEXT, SCM chicken, PYP3, CLOJ, R, COB, FS|
Fetching successful submissions
If you are still having problems, see a sample solution here.