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
2017-05-05 18:07:19
what is to be done in the problem?? can anybody explain clearly??
2017-01-08 19:07:02
Using Python for Ideone.com judges is a nightmare
2016-12-06 09:54:39 Sahil Patel
Once you understand the problem, code is fairly procedural. For those Not getting 10, note that the tuples 'may' be of 6 characters. It's not fixed.
2016-09-25 07:37:51
how to get a(blue bit) and b(green)bit ??
2016-06-02 21:23:03 Yogesh Dorbala
Though its running fine on ideone, its throwing a run time error in myStatus :| Any idea on what to do?
2016-05-08 09:15:26 Dennis Slater
Looks simple but is pretty tough. Not tricky though. Got it on first try after quite a bit of work. Manipulating the inputs was the toughest part for me.
2016-02-12 18:34:10
omg, that one was tough...
2016-02-01 15:44:07 Nguyễn Hoàng Nam
keanedawg: shouldn't the 64-character-long line be kept in string rather than array?
2016-01-24 23:59:26
It took me a while to understand what this is saying, basically, if the a(blue bits) == 55, then look at 55th letter in the 64 letter string to find the first letter k.

However, it is the 55th assuming the values are in an array starting at 0. Technically, k is the 56th letter not the 55th. But in an array starting at 0, it is the 55th.

Last edit: 2016-01-24 23:59:57
2016-01-24 10:03:59
I think you don't get points for any of the basic problems
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.