玄关，时间开销都用哪了？感觉离跑出1.5s差得远

#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;
int q;
long long l,r;
vector<int> genshin;
//数据范围太大没办法开10的9次方的数组统计1~n的个数
//但是可以直接爆搜符合条件2的数字，然后再检验是不是素数，按顺序放到数组里
//最后二分查找返回下标差值即可
bool vis[10];
long long P[]={2,7,61};  //int型MR测试数据
long long val;  //当前数值
long long quickpow(long long a,long long t,long long mod)   //注意：当数据范围不超过1e9时不需要关心溢出问题，否则要考虑128位整形
{
    long long res=1;
    while(t)
    {
        if(t&1) res*=a%mod,res%=mod;  //res%=mod忘了也是人才
        t>>=1;
        a*=a%mod,a%=mod;  //还有a%=mod这两句默写114514遍！！！！！！！
    }
    return res%mod;  //带模数的快速幂
}
bool MRtest(long long a,long long p)  
{
    long long n=p-1;  //将p-1拆成t*2^h的形式,直到剩下的t为奇数
    long long h=0;
    while(n%2==0) n>>=1,h++;  //h+1也代表这堆数的个数
    long long t=n; //剩下的t
    long long x=quickpow(a,t,p),y;
    for(int i=1;i<=h;i++)  //类似双指针循环，次数为个数-1即h+1-1
    {
        y=quickpow(x,2,p);  //后面的数一定是前面的数的平方
        if(y==1 && x!=1 && x!=p-1) return true;  //出现1，前面必然出现1或p-1（二次探测定理）
        x=y;
    }
    if(x!=1) return true;   //反正x被y赋值了写x写y都无所谓
    return false;
}
void isprime(long long n)  //判断生成的满足条件2的数是否是质数，是就放进vector里
{
    if(n<=1) return;
    if(n==2) {genshin.push_back(val);return;} 
    if(n%2==0) return;
    for(int i=0;i<3;i++)
        if(P[i]==n) {genshin.push_back(val);return;}  //这一句一定要加，否则判断不了P[i]自己
        else if(MRtest(P[i],n)) return;  //测出来是合数就返回
    genshin.push_back(val);  //否则就是质数
}
void dfs(int curr,int len,long long off)  //curr表示下次要决定数位（从最低位开始）,len表示数位限制,off=10^(curr-1)
{
    if(curr>len)
    {
        isprime(val);
        return;
    }
    for(int i=0;i<=9;i++)
    {
        if(curr==len && i==0 || vis[i]) continue;
        val+=i*off;
        vis[i]=1;
        dfs(curr+1,len,off*10);
        vis[i]=0;
        val-=i*off;
    }
}
int main()
{
    scanf("%d",&q);
    for(int i=1;i<=9;i++) dfs(1,i,1);   //还是太慢,i=9就T
    sort(genshin.begin(),genshin.end());   //vector的排序！！
    /*
    for(vector<int>::iterator it=genshin.begin();it!=genshin.end();it++)
        cout<<*it<<" ";
    cout<<endl;
    */
    while(q--)
    {
        scanf("%lld%lld",&l,&r);
        printf("%lld\n",upper_bound(genshin.begin(),genshin.end(),r)-lower_bound(genshin.begin(),genshin.end(),l) );
    }
    return 0;
}