Честная игра с криптографией
Шифрование — это процесс преобразования открытого текста в шифротекст. Один из методов — шифр Плейфера, изобретенный Чарльзом Уитстоном в 1850-х годах и названный в честь его сторонника, шотландского ученого Лайона Плейфера. В отличие от многих шифров подстановки, шифр Плейфера шифрует не отдельные буквы, а пары букв, называемые диграфами. Процесс шифрования использует 5×5 сетку, созданную с помощью секретного ключа, известного только двум сторонам. Сетка формируется следующим образом: буквы ключа записываются по одной в каждый квадрат сетки, начиная с верхнего ряда. Повторяющиеся буквы в ключе пропускаются. Затем оставшиеся буквы алфавита заполняют свободные квадраты, при этом I и J занимают один квадрат. Например, если ключ — "ECNA PROGRAMMING CONTEST", сетка будет выглядеть так:
Шифрование диграфа происходит по следующим правилам:
Если обе буквы находятся в одной строке, замените каждую на букву справа (с переходом в начало строки). Например, в приведенной сетке диграф DS шифруется как FB, а AP — как PE.
Если обе буквы в одном столбце, замените каждую на букву ниже (с переходом в начало столбца). Например, PF шифруется как IU (или JU), а WO — как CS.
В противном случае "сдвиньте" первую букву по строке до столбца второй буквы и наоборот. Полученные буквы — это зашифрованные символы диграфа. Если исходный диграф — углы прямоугольника в сетке, замените их символами в других углах. Например, TU шифруется как FH, UT — как HF, а ZC — как WP.
Что делать, если диграф содержит две одинаковые буквы? В оригинальном шифре Плейфера между ними вставляется 'X', и шифрование продолжается. Также добавляется 'X' в конце открытого текста, если количество букв нечетное. Например, открытый текст "OOPS" преобразуется в диграфы "OX", "OP", "SX" и шифруется как "GWICBW" (с использованием приведенной сетки). Открытый текст "POOS" не требует добавления букв, так как 'O' не повторяются в одном диграфе.
Мы модифицируем шифр Плейфера: вместо 'X' используйте 'A' при первой вставке, затем 'B' и так далее (исключая 'J'; после 'I' идет 'K'). После 'Z' возвращайтесь к 'A'. Если вставленная буква создает диграф с одинаковыми буквами, переходите к следующей. Например, "OOPS" станет "OA", "OP", "SB", а "AABCC" — "AB", "AB", "CD", "CE".
Дан ключ и открытый текст, необходимо сгенерировать соответствующий шифротекст.
Входные данные
Входной файл начинается с целого числа n, указывающего количество задач. Каждая задача состоит из двух строк: первая содержит ключ, вторая — открытый текст для шифрования. Обе строки могут содержать буквы верхнего и нижнего регистра, а также пробелы и неалфавитные символы (которые следует игнорировать). Для простоты буквы 'j' и 'J' не будут встречаться ни в ключе, ни в открытом тексте.
Выходные данные
Для каждой задачи выведите номер случая, за которым следует соответствующий шифротекст, используя заглавные буквы без пробелов. Всегда используйте букву 'I' вместо 'J' в шифротексте.