Your task is to decrypt a cipher 'S'.

A Cipher will have characters from A-Z only.
A 'N' length Key will also given as input in which each index of Key[i] will have two values X and Y (Key[i]->first = X, Key[i]->second = Y).

Algorithm to decrypt is givem below:

• Take a string and add underscore characters at the end to increase the length of the string to a perfect square.
• Arrange the characters row-wise in a square matrix(NOTE TOP LEFT CELL WILL BE (1,1) ).
• For every index of key, swap coloumn X with coloumn Y.
• Read out the characters row-wise from the matrix ignoring the underscores.

INPUT FORMAT:

First line of input contains single integer T denoting the number of test cases.
The first line of each test case contains a Cipher string 'S'.
The second line of each test case contains the length of key 'N'
Following N lines, each line contains space seperated X and Y

OUTPUT FORMAT:

Deciphered String

CONSTRAINTS:

1<=T<=10
1<=|S|<=100000
1<=N<=100000
X and Y can have all possible coloumns of valid matrix 

Problem Setter: Shlok Singh