Back

DNA Sequencing

Worth 2 point(s) - Runtime Limit: 1 seconds

Introduction

If you have even the slightest amount of knowledge in the field of biology, then you should know that all life on Earth is coded by deoxyribonucleic acid, or DNA. Genetic information is stored in DNA as a long double helix of 4 nucleotide bases - adenine, cytosine, guanine, and thymine. Since the human genome has billions of bases within it, the base names are often shortened to A, C, G, and T. As mentioned, DNA is a double helix, a shape that resembles a twisted ladder. Each “rung” of the ladder is made of 2 bases that have bonded together. These bases bond in very predictable ways, such that A always bonds with T (and vice versa) and C always bonds with G (and vice versa).

With this pattern, it is easy to predict the sequence of bases on a strand of DNA when given the sequence of the complementary strand. For example, given the sequence ATCTGACTG, we can say that the complementary strand would be TAGACTGAC, because T bonds with A, A bonds with T, G bonds with C, and so on. Of course, doing this for billions of nucleotides would be tedious, so why not have a computer do it for you?

Input:
The first line in an integer D denoting the number of test cases. The next D lines each have an integer L that denotes the length of the sequence, followed by a space and the sequence of nucleotides.

Output:
For each test case, output the nucleotide sequence of the complementary strand.

Sample Input

3
9 ATCTGACTG
9 TATTCCCGA
5 ATGCA

Sample Output

TAGACTGAC
ATAAGGGCT
TACGT