#301. 【NFLSPC #1】Problemsetting

题目类型:传统型 时间限制:1000 ms 空间限制:512 MiB
输入文件:标准输入 输出文件:标准输出 答案检查器:文本比较

你成为了咕特色鸽(GTSG) 2019的出题人,为了区分天上第一选手和其他选手之间的差距,你造了一个月,终于在ddl前出了一道毒瘤题放在了D2T3。D2结束,果然,只有JS-001一台电脑上写了T3的程序。你打开他的成绩单,却意外发现只有200分,并没有通过你的题。你手动重测了一下该题,发现当输入的数 $n$ 满足 $\sigma_0(n)\ =\ 1\ \bmod\ 2$ 时答案与你的std不符。你冷静分析,LGM怎么可能不ak,肯定是std错了,然而如果现在修改std恐怕来不及,为了防止出现D3,你决定修改数据!

具体地,你每次可以选择对数字 $x$ 进行一下两种操作中的一种:

  1. 将 $x$ 10进制表示下(不含前导 $0$)的一个数字修改成 $0,\ 1,\ ...,\ 9$ 中的一个。例如 $123$ 可以变成 $133$;$1001$ 可以变成 $1,\ 1000$。

2.将 $x$ 10进制表示下(不含前导 $0$)的一个数字删去。例如 $123$ 可以变成 $23,\ 13$;$1001$ 可以变成 $1,\ 100$。

为了防止被发现,你每次修改后的数字 $x$ 必须要保证 $x$ 是正整数

你的数据有 $T$ 行,每行有一个数 $x$,你希望尽可能快地(用尽可能少地操作)将 $x$ 变成 $y$ 使得 $\sigma_0(y)\ =\ 0\ \bmod\ 2$。对于每个数 $x$,输出最少的操作次数。

其中 $\sigma_0(n)$ 表示 $n$ 的约数个数,例如 $\sigma_0(1)\ =\ 1,\ \sigma_0(2)\ =\ 2,\ \sigma_0(3)\ =\ 2,\ \dots$。


输入格式

第一行输入一个整数 $T$。

接下来 $T$ 行,每行一个正整数 $x$。

输出格式

输出 $T$ 行,每行一个数表示最少操作次数。若无法修改,则输出 $-1$。


样例

input
3
1
35
10
output
1
0
0
解释

$1$ 通过一次第一种操作可以变成 $2$,$\sigma_0(2)\ =\ 2$。

$\sigma_0(35)\ =\ 4$。

$\sigma_0(10)\ =\ 4$。


限制与约定

  • Subtask $1$($50\%$):$1\ \leq\ T,\ x\ \leq\ 10000$;
  • Subtask $2$($50\%$):$1\ \leq\ T\ \leq\ 10000,\ 1\ \leq\ x\ \leq\ 10^{18}$。

$by\ \text{King_George}$