#XXSY26JAT3. 红军的密电

红军的密电

红军的密电

题目描述

红军长征途中,通讯班需要向总指挥部发送关键的战报密电。为了防止敌军破译,红军的密码本是基于“素数”(质数)构建的。

根据密电规则,每次发送的校验码 N(N > 3),必须由两个素数密令 A 和 B 组合而成,并且校验码 N 必须恰好是 A 和 B 的算术平均数。也就是说: N=A+B2\frac{A+B}{2}

请你编写程序,帮助小通讯员根据给定的 N 计算出有多少组符合条件的素数 A 和 B。

输入格式

第一行输入一个整数 T,表示测试用例的数量。

接下来 T 行,每行包含一个整数 NiN_i。

输出格式

​ 输出 T 行,对于输入数据中的每一个 NiN_i,输出满足NiN_i=Ai+Bi2\frac{A_i+B_i}{2} 且 AiA_i<=BiB_i的 AiA_i与的BiB_i组数。

输入输出样例

4
8
4
7
21
2
1
2
4

2
234543
32
4437
5

数据规模与约定

40% 的数据:对于 1 <= i <= T,4 <=NiN_i<= 100

100% 的数据:1 <= T <= 100,对于 1 <= i <= T,4 <= NiN_i<= 10000000