C0540 红军的密电

红军的密电

题目描述

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

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

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

输入

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

接下来 T 行，每行包含一个整数Ni 。

输出

输出 T 行，对于输入数据中的每一个 Ni ，输出满足Ni = (Ai +Bi)/2且Ai<=Bi的 Ai 与Bi的组数。

数据范围

40% 的数据：对于 1≤i≤T，4≤Ni≤100

100% 的数据：1≤T≤100，对于 1≤i≤ T，4≤Ni≤10^7

输入样例1

4
8
4
7
21

输出样例1

2
1
2
4

输入样例2

2
1000
999

输出样例2

37
56

输入样例3

2
234543
32

输出样例3

4437
5