{"trustable":true,"sections":[{"title":"","value":{"format":"MD","content":"The sequence **011212201220200112...** is built next way: first goes **0**, then the next action is repeated: append the already existing sequence to the right, replacing **0** with **1**, **1** with **2** and **2** with **0**, i.e.\r\n\r\n`0 → 01 → 0112 → 01121220 → ...`\r\n\r\nFind the **m**-th digit of the sequence.\r\n\r\n#### Input\r\nFirst line contains the number of tests **n** (**1** ≤ **n** ≤ **1000**). Each of the next **n** lines contains **m** (**1** ≤ **m** ≤ `2^63` - **1**) - the number of required digit in the sequence.\r\n\r\n#### Output\r\nFor each test case print in a separate line the digit at the **m**-th place in the given sequence."}},{"title":"Example","value":{"format":"HTML","content":"\u003ctable class\u003d\u0027vjudge_sample\u0027\u003e\n\u003cthead\u003e\n \u003ctr\u003e\n \u003cth\u003eInput\u003c/th\u003e\n \u003cth\u003eOutput\u003c/th\u003e\n \u003c/tr\u003e\n\u003c/thead\u003e\n\u003ctbody\u003e\n \u003ctr\u003e\n \u003ctd\u003e\u003cpre\u003e3\n17\n239\n385\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e1\n0\n2\n\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n"}}]}