题目描述

给出一个只包含小写字母和问号的、长度为 $n$ 字符串 $s$，你需要把其中的每个问号替换成任意一个小写字母。 你需要判断，对于所有可能的替换方案，$s$ 属于哪一类： $\hspace{23pt}\bullet\,$不论如何替换，替换后的字符串一定是回文串； $\hspace{23pt}\bullet\,$不论如何替换，替换后的字符串一定不是回文串； $\hspace{23pt}\bullet\,$存在一种方案使得替换后的字符串是回文串，且也存在一种替换方案使得替换后的字符串不是回文串。 【名词解释】 回文串：一个字符串被称作回文串，当且仅当这个字符串从左往右读和从右往左读是相同的。官方中文

输入格式

每个测试文件均包含多组测试数据。第一行输入一个整数 $t\ (1\le t\le 10^4)$ 代表数据组数，每组测试数据描述如下：官方中文

第一行输入一个整数 $n\ (1\le n\le 5\times10^5)$，表示字符串的长度。 第二行输入一个只包含小写字母和问号、长度为 $n$ 的字符串 $s$，表示初始的字符串。官方中文

除此之外，保证单个测试文件的 $n$ 总和不超过 $5\times10^5$。官方中文

输出格式

对于每组测试数据，新起一行。根据下面三种情况，输出一行一个字符串： $\hspace{23pt}\bullet\,$若无论如何替换，替换后的字符串一定是回文串，输出 $\tt certainly$； $\hspace{23pt}\bullet\,$若无论如何替换，替换后的字符串一定不是回文串，输出 $\tt impossible$； $\hspace{23pt}\bullet\,$若存在一种方案使得替换后的字符串是回文串，且也存在一种替换方案使得替换后的字符串不是回文串，输出 $\tt possible$。官方中文