给定由数字 组成的表示一个整数的字符串 s (整数可以是由 开头的,字串长度为 )，假设允许在两个数字之间插入一个加号，或者插入一个减号，或者不插入任何加减号。统计根据以上三种变换得到的所有算式的运算结果能被某一个一位质数整除的不同方案数。
输入格式
第 1 行：整数 为问题数。
第 2~T+1 行：每行是一个问题的字符串 (长度为 )。
输出格式
对于每个问题，在一行中输出满足条件变换种类数。由于答案可能很大，输出对 取模后的结果。
提示
对于 s=123，变换有
- 1+2+3
- 1-2+3
- 1+2-3
- 1-2-3
- 123
- 12+3
- 12-3
- 1+23
- 1-23
共 种，这 个算式的计算结果全部能被 或 整除，因此符合条件的变换种类数是 。