ll dp[20][2];

ll solve(ll n){
    memset(dp, 0, sizeof(dp));
    string s = _to_string(n);
    bool has = false;
    for(int i = 0; i < (int) s.size(); i++){
        for(int j = 0; j + '0' < s[i]; j++){
            dp[i][j == 3 || has]++;
        }
        if(i + 1 < (int) s.size()){
            dp[i + 1][0] += dp[i][0] * 9;
            dp[i + 1][1] += dp[i][0] + dp[i][1] * 10;
        }
        if(s[i] == '3')
            has = true;
    }
    return dp[(int) s.size() - 1][1];
}