Today, I learned Digit DP for the first time, so I tried to solve different kinds of Digit DP problems. While doing that, I came upon This question. I know this is not a Digit Dp question, and there is a much better approach to this question. However, I wrote a solution using the concepts I learned and got TLE on Test Case 5. Can Someone help me optimize this further?

Here is the code :

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
template<class T> using oset = tree< T , null_type , less<T> , rb_tree_tag , tree_order_statistics_node_update >; 
// *st.find_by_order(i) --> element at ith position
// st.order_of_key(x) --> no. of ele less than x
//For multiset change less to less_equal and for reverse order change less to greater
#define int long long 
#define endl '\n'
#define all(x) (x).begin(), (x).end()
template<typename T> // cin >> vector<T>
istream& operator>>(istream &istream, vector<T> &v){for(auto &it : v)cin >> it;return istream;}
template<typename T> // cout << vector<T>
ostream& operator<<(ostream &ostream, const vector<T> &c){for(auto &it : c)cout << it << " ";return ostream;}

// int dp[19][2];
map<tuple<int, bool, string>, int> memo;

int f(int idx , bool bound , string ans , int x , string &s) {
    if(idx == (int)s.size()) {
        int y = stoll(ans);
        if(y == 0 or (x == y)) return 0;
        int div = x ^ y;
        return (x % div == 0) or (y % div == 0);
    }
    auto state = make_tuple(idx, bound, ans);
    if (memo.find(state) != memo.end()) return memo[state];
    // if(dp[idx][bound] != -1) return dp[idx][bound];
    int res = 0;
    int maxDigit = 9;
    if(bound) maxDigit = s[idx] - '0';
    for(int i = 0 ; i <= maxDigit ; i++) {
        res += f(idx + 1 , bound & (i == maxDigit) , ans + to_string(i) , x , s)   ;
    }
    // return dp[idx][bound] = res;
    return memo[state] = res;
}

signed main()
{
    ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
    int testCase; cin >> testCase;
    while(testCase--) {
        memo.clear();
        int x , m;
        cin >> x >> m;
        string s = to_string(m);
        string ans = "";
        // memset(dp , -1 , sizeof(dp));
        cout << f(0 , true , ans , x , s) << endl;
        memo.clear();
    }
    return 0;
}

Any help is highly appreciated, my friend!