All submissions for this problem are available.
Sandip and Servesh are best friends. One day Sandip challenges Servesh to decrypt
a large binary number("number containing 0's and 1's only") given in the form of a string.
Beacause Sandip knows Servesh well, he remembers that Servesh is good with Binary Numbers.
So, he wants to make the question more interesting for him and therefore he converted the
binary number into it's equivalent quaternary number("Quaternary is the base-4 numeral system.
It uses the digits 0, 1, 2 and 3 to represent any real number") and gave it to Servesh
in form of string.
Sandip gave small hint to Servesh to decrypt the given string, which is as follows:
Suppose decimal conversion of given string is R. Now R is divided by power of 2 i.e (2^i, i=1,2,...k) till 2^i<=R. Let the remainders after divisions are r1,r2....,rk respectively.So, the decrypted string will be the frequency of these remainders in respective order of occurrence. See example for more clarification.
Note: Output Empty String, if it is not possible to generate decrypted string.
The first line of input consists of T denoting the total number of testcases.
Each testcase consists of two lines.
First line consists of an integer N denoting the length of the Quaternary number.
Second line consists of Quaternary number.
For each test case, print the output as described.
- 1 ≤ T ≤ 100
- 1 ≤ N ≤ 100000
Input: 3 2 23 2 32 3 211 Output: 12 111 23
Quaternary number is 23.Now Decimal Representation of 23 will be 11(2*41+3*40).11 is divided by 2,4,8(powers of 2) till (powers of 2)<=11 and remainders will be 1,3,3 respectively.So, final decrypted string will be 12(Frequency of 1 is 1 and Frequency of 3 is 2 in this case).
|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, SCALA, 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, PERL6, TEXT, SCM chicken, CLOJ, FS|
Fetching successful submissions