疯狂科学家 Byteasar 想要培育一种新型生物。为此，他决定修改一只 Bytean 小鼠的基因组。

DNA 可以描述为由字母 A、C、G 和 T 组成的核苷酸序列。Byteasar 的宏伟计划非常简单：利用小鼠的 DNA，他要创造出一条长度相同的新 DNA，使其与小鼠 DNA 的相似度尽可能低。两条 DNA 的相似度定义为它们的最长公共子序列的长度。两个词 $x, y$ 的最长公共子序列定义为可以通过从两个词中删除若干（可能为零）字母后得到的长度最长的词。（注意：两个词可能有多个最长公共子序列。例如，词 CACCA 和 CAAC 的最长公共子序列是 CAA 和 CAC。）请编写一个程序来计算出符合要求的 DNA。

输入格式

第一行包含一个整数 $n$ ($1 \le n \le 10\,000$)，表示 Bytean 小鼠 DNA 的长度。第二行包含 DNA 中核苷酸的描述：一个由大写字母 A、C、G、T 组成的序列。

输出格式

第一行应包含一个整数：Bytean 小鼠的 DNA 与你程序计算出的 DNA 之间的相似度。第二行应包含一个由字母 A、C、G、T 组成的序列。这应该是与输入 DNA 相似度尽可能低的一条 DNA。如果存在多个正确答案，你的程序可以输出其中任意一个。

样例

输入 1

4
GACT

输出 1

1
TCAG