HS12HDPW - Hidden Password

You are given two alphanumeric ASCII strings. An ancient manuscript says those strings contain a hidden password. Decode it!

The first string may be grouped into tuples of six characters each. For each such 6-tuple, taking from the i-th character (start counting from 0) the i-th bit of its ASCII code gives you a number (call it a), and likewise taking the ((i+3) mod 6)-th bits gives you another number (call it b).

These two numbers tell you about the next two characters to be included in the password, namely the a-th and the b-th character from the second string (count starting from 0 as usual).

Input

First, you are given t (t < 100) - the number of test cases.

Each of the test cases starts with one number n (n < 100) - the number of 6-tuples in the first string, followed by the two strings in separate lines (please have a look at the example to see the correct format). The second string is 64 characters long.

Successive test cases are separated by an empty line.

Output

For each of the test cases, output its hidden password in a separate line.

Example

Input:
2
2
qwe345 rf3Arg
XSBSRasdew9873465hkldsfsalndfvnfq489uqovkLKJHaeDaae555Sk5asdpASD

3
2S4J5K 111111 lrtb2A
isimgsow45ipfgisd56wfgngdfcdkgc7kKKKkuuJJgfstdygQdWORQADFSLKF2K8

Output:
keep
coding

Explanation

Let us have a look at the first 6-tuple: qwe345.

char. ASCII code
  q   113 = 01110001B
  w   119 = 01110111B
  e   101 = 01100101B
  3    51 = 00110011B
  4    52 = 00110100B
  5    53 = 00110101B

a (blue bits) = 110111B = 55

b (red bits) = 101110B = 46


Added by:kuszi
Date:2012-09-10
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64
Resource:High School Programming League 2012

hide comments
2023-07-16 20:27:23
The description of this problem is simply horrible. The only way to understand the goal here is by studying the example. Author's english could use some serious practice.
2022-07-16 18:11:05
Well frommy understanding the goal is basically to extract the passwords from the 64 character long string (counting from 0). The indexes for the password characters are gotten from the 6-tuple given.
As shown in the explanation the first the index 55 of the second string is "k" which is the first character of the password, the next is 46 which if you count from the second string gives e.
If you proceed with the second 6-tuple you'll get 50 and 60 which corresponds to "e" and "p" giving you the first password "keep"; So basically each 6-tuple gives two characters for the password.

P.S Just came across it and haven't done it yet, that's just what I understood from the information given :)
2020-04-30 22:58:35
Would be easy if author explained it better.
2018-05-07 03:12:17
Statement contains a typo, but it's obvious from the example case that we're supposed to use (i+3)%6 -th bit.
2018-05-06 20:39:02
Wait, you're supposed to iterate for all 6 tuples! I see. Nevermind!

Wait, WTF????? If you apply their transformation i+3%6, it doesn't get you the right answer... Some weird rollover (it rolls over back to 0 if i+3%6 > 6)

The question clearly states that taking the i+3%6th bit of the ith character will get you the right answer, but it's obviously not! If you simply apply that transformation, you'll QUICKLY overflow the array bounds, so there's obviously some sort of rollover, WHICH IS NOT DESCRIBED IN THE PROBLEM! For example, for i=6 (the last case in the example), if you simply applied the transformation you were told to use, you would get 6+3%6=9, WHICH OVERFLOWS THE BINARY ARRAY!

YES GOT IT!!!! Problem is, I had to write a custom function map to actually MAP the value of the i+3%6 transformation to the correct array address, which is f(x) = x-6 if x>5, x otherwise (x is the value of i+3%6)... TBH, not a very well written problem, it didn't describe or even mention the rollover. aah well...

Last edit: 2018-05-06 21:57:00
2018-05-06 20:34:51
?
I know how to get the first 2 characters, but what about the next ones?
2017-11-27 10:15:46
Attention: "Successive test cases are separated by an empty line."
2017-10-16 20:55:05
First try, this was a good lesson!
2017-10-12 12:38:39
plz someone explain it?
2017-07-26 09:42:10
Once you understand the question, its easy. C++ STL Bitset was helpful for solving this problem.
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.