PIPI很喜欢质数，他现在有一个数x，想知道最少经过几步操作能够把该数变成一个质数。
对于每步，他可以从下面3种操作中选取一种来执行：
（1）把当前数加1
（2）把当前的数除以2（向下取整）
（3）把当前数各数位的数加1后相乘（如431变成5*4*2=40）

第一行输入测试用例组数t（t<=1000)。
接下来t行，每行输入一个正整数x(x<=1e8）。

对于每组输入，输出x能变成质数的最小操作步数。