In an ancient civilization, shrouded in the mists of time, there existed a group of mathematicians known for their profound wisdom and unparalleled understanding of the universe. These sages believed that the true essence of knowledge was encapsulated within the mystical properties of prime numbers. To safeguard their discoveries and ensure that only the worthy could access their profound insights, they devised an ingenious cipher.
This cipher, a marvel of mathematical ingenuity, was based on secret prime numbers and their unique properties. It was said that these numbers held the keys to unlocking unparalleled technological advancements, advancements so profound that they could drastically alter the course of human history. The mathematicians encoded their most significant discoveries and secrets using this cipher, where each letter's alphabetical position (A=0, B=1,..., Z=25) was used to form a unique number for each word. The encoded number then pointed to a specific position in the sequence of prime numbers, which was believed to hold the ultimate truth and wisdom.
The encoding process involved assigning each letter of the alphabet a specific value, starting from A=0 to Z=25, thereby transforming words into unique numerical codes. This process used a unique formula, similar to creating a number from its digits. The first letter of a word acts like the first digit, and each letter is multiplied by 10 raised to a power that depends on its position in the word. This method turns words into distinct numbers. For example, to encode the word "XYZ", they applied the formula , where X, Y, and Z corresponded to the alphabetical positions of the letters. Thus, "XYZ" became . The true magic unfolded in the next step: this numerical code was not the message itself but a pointer to it. The actual secret was the prime number at the 2565th index (0 based indexing, prime[0]=2, prime[1]=3...), which, in this case, is 23011. Hence, the word "XYZ" was a veil, concealing the prime number 23011—a fragment of the ancients' lost wisdom. Another example, take the word “DJ”, according to formula, , so, 39th prime number in 0 based indexing is 173.
Centuries later, a curious soul, an expert in ancient languages and cryptography, stumbles upon remnants of this civilization's knowledge. Intrigued by the mathematical elegance of the cipher and driven by a desire to unlock the ancients' secrets, the protagonist embarks on a quest to decode the messages left behind. The task is to apply the ancient formula to encode words into numbers and then discover the corresponding prime number, a gateway to understanding the lost knowledge.
There will be “T” number of test cases, each containing “N” words encoded using the ancient mathematicians' method. The challenge is not merely one of translation but of connection—bridging the vast expanse of time to recover the technologies and insights that were once within humanity's grasp.
Constraints:
1 ≤ T ≤ 100
1 ≤ N ≤ 100
1 ≤ length of each word ≤3
Note: All input words will be provided in UPPER CASE letters only.
Input
2
3
XYZ
DIU
BD
2
B
SWE
Output
23011
2749
43
3
17609
Sample
| Input | Output |
|---|---|
2 3 XYZ DIU BD 2 B SWE | 23011 2749 43 3 17609 |
