Under construction

Still being built. Things may change

Affine Cipher

Interview

Time limit5sMemory limit256 MB

Summary
Apply E(X) = (aX + b) mod 26 to each uppercase letter of the plaintext and print the ciphertext.
Level

Easy1 of 10

Topics
Implementation, String, Math
Solved
No attempts yet

Problem

Jeongeun, trained in the western country, slipped into the eastern country. After getting hold of the eastern country's information, Jeongeun decided to use an affine cipher to send it back west safely.

An affine cipher is computed with this formula.

E(X)=(aX+b) mod 26E(X) = (aX + b) \bmod 26

Map the letters A through Z to 0,1,2,…,250, 1, 2, \dots, 25 in order. With a=3a = 3 and b=1b = 1, feeding the letter A into the formula gives E(0)=(3×0+1) mod 26=1E(0) = (3 \times 0 + 1) \bmod 26 = 1, so the encrypted result is B.

Given aa, bb, and a plaintext made only of uppercase letters, write a program that turns the plaintext into ciphertext.

Input

The first line has the number of test cases TT (1≤T≤501 \le T \le 50).

The first line of each test case has two integers aa and bb (0<a,b≤1 000 0000 < a, b \le 1\,000\,000). aa is coprime with 26.

The second line of each test case has the plaintext ss. Its length ∣s∣|s| is greater than 0 and less than 1 000 0001\,000\,000, and ss consists only of uppercase letters.

Output

For each test case, print the ciphertext of ss on its own line.

Examples3

  1. Example 1

    Input
    2
    3 1
    IAMSPY
    5 3
    ABCDEFGHIJKLMNOPQRSTUVWXYZ
    
    Expected output
    ZBLDUV
    DINSXCHMRWBGLQVAFKPUZEJOTY
    
  2. Example 2

    Input
    1
    1 26
    HELLOWORLD
    
    Expected output
    HELLOWORLD
    
  3. Example 3

    Input
    1
    25 25
    ABCDEFGHIJKLMNOPQRSTUVWXYZ
    
    Expected output
    ZYXWVUTSRQPONMLKJIHGFEDCBA