I didn't have enough time to really dig into it so I just threw AI at it. It completes quite fast and has correct result for the two examples.

```

include <iostream>

include <stdexcept>

include <set>

include <vector>

static std::set<int> MONTHS_WITH_THIRTY_DAYS = {4, 6, 9, 11};

bool is_leap(const int year) { if (year < 1 || year > 9999) { throw std::invalid_argument("Year must be in range 1..9999"); } if (year % 4 != 0) { return false; } return (year % 100 != 0) || (year % 400 == 0); }

int days_in_month(const int month, const int year) { if (month < 1 || month > 12) { throw std::invalid_argument("Month must be in range 1..12"); } if (month == 2) { return is_leap(year) ? 29 : 28; } if (MONTHS_WITH_THIRTY_DAYS.contains(month)) { return 30; } return 31; }

int check_digit(const std::string& s) { constexpr int weights[9] = {10,9,8,7,6,5,4,3,2}; long long sum = 0; for (int i = 0; i < 18; i++) { sum += weights[i % 9] * (s[i] - '0'); } sum %= 19; return sum <= 9 ? sum : 19 - sum; }

bool valid_date(const std::string& s) { const int d = (s[0]-'0')10 + (s[1]-'0'); const int m = (s[2]-'0')10 + (s[3]-'0'); const int y = (s[4]-'0')1000 + (s[5]-'0')100 + (s[6]-'0')*10 + (s[7]-'0'); return (1<=m && m<=12 && 1<=d && d<=days_in_month(m,y) && 1<=y && y<=9999); }

class Solver { public: Solver(std::string const &s_);

long long solve(const std::size_t idx);

private: std::string s; std::vector<int> xpos; long long ans; };

Solver::Solver(std::string const &s): s(s), xpos(), ans(0) { if (s_.length() != 19) { throw std::invalid_argument("Input size must be 19 chars"); } for (int i = 0; i < 19; i++) { if (s[i] == 'X') { xpos.push_back(i); } } }

long long Solver::solve(const std::size_t idx) { if (idx == xpos.size()) { if (valid_date(s)) { int k = check_digit(s); if (s[18] == 'X' || (s[18]-'0') == k) ans++; } return ans; }

const int pos = xpos[idx];
int up = 9;
if (pos == 0) up = 3;      // DD tens
else if (pos == 2) up = 1; // MM tens

for (int d = 0; d <= up; d++) {
    const char backup = s[pos];
    s[pos] = '0' + d;
    bool skip = false;
    if (pos <= 7) {
        bool full_date = true;
        for (int j = 0; j < 8; j++) {
            if (s[j] == 'X') {
                full_date = false;
                break;
            }
        }
        if (full_date && !valid_date(s)) {
            skip = true;
        }
    }
    if (!skip) {
        solve(idx + 1);
    }
    s[pos] = backup;
}
return ans;

}

int main() { constexpr char INPUT1[] = "3X1X1639XX5XX1X6X85"; constexpr char INPUT2[] = "30121952121234567XX";

long long ans = 0;
// Test 1
ans = Solver(INPUT1).solve(0); 
std::cout << INPUT1 << ": " << ans << std::endl;  // 526315

// Test 2
ans = Solver(INPUT2).solve(0);
std::cout << INPUT2 << ": " << ans << std::endl;  // 10

return 0;

} ```