F

#include <algorithm>
#include <iostream>
#include <map>

using namespace std;

#define int long long

signed main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    int t;
    cin >> t;
    while (t--) {
        int s, l, r, k;
        cin >> s >> l >> r >> k;
        string v = to_string(s);
        map<int, int> dp[v.size()][k + 1];
        for (int i = 0; i < v.size(); ++i) {
            for (int j = i - 1; j >= -1; --j) {
                for (int d = 1; d <= k; ++d) {
                    int cur = stoll(v.substr(j + 1, i - j));
                    if (v[j + 1] == '0' && i - j > 1) {
                        continue;
                    }
                    if (j == -1) {
                        dp[i][1][cur] = 1;
                        continue;
                    }
                    for (int p = cur - r; p <= cur - l; ++p) {
                        if (dp[j][d - 1].find(p) != dp[j][d - 1].end()) {
                            dp[i][d][cur] += dp[j][d - 1][p];
                        }
                    }
                    for (int p = cur + l; p <= cur + r; ++p) {
                        if (dp[j][d - 1].find(p) != dp[j][d - 1].end()) {
                            dp[i][d][cur] += dp[j][d - 1][p];
                        }
                    }
                }
            }
        }
        int sum = 0;
        for (auto i : dp[v.size() - 1][k]) {
            sum += i.second;
            // cout << i.first << ' ' << i.second << '\n';
        }
        cout << sum << '\n';
    }

}