C0581 红军的强质数密码
红军的强质数密码
题目描述
为了加强密电的安全性，红军通讯班采用了更为复杂的“强质数”校验规则。一个质数如果它的各位数字之和也是一个质数，那么这个质数被称为“强质数”。
每次发送情报时，指挥员会给出一个上限 N，需要统计在 2 到 N 的范围内有多少个“强质数”。请你编写程序，根据输入的 N 快速给出答案。
输入格式
第一行包含一个整数 T，表示测试用例的数量。
接下来 T 行，每行包含一个整数 Ni。
输出格式
输出 T 行，对于每个 Ni，输出一行，包含一个整数，表示 [2, Ni] 中“强质数”的个数。
数据范围
40% 的数据：1≤T≤100，2≤Ni≤1000
100% 的数据：1≤T≤100，2≤Ni≤10^7
输入样例#1
3
10
20
30
输出样例#1
4
5
7
输入样例#2
2
100
50
输出样例#2
21
13