#include <bits/stdc++.h>

#define all(x) (x).begin(), (x).end()
#define fr first
#define sc second
#define m_p make_pair
#define low_bo(a, x) ((int)(lower_bound(a.begin(), a.end(), x) - a.begin()))
#define up_bo(a, x) ((int)(upper_bound(a.begin(), a.end(), x) - a.begin()))
#define unique(a) a.resize(unique(a.begin(), a.end()) - a.begin())
#define popcnt(x) __builtin_popcount(x)
#define shuffle(a) shuffle(a.begin(), a.end(), rnd)

using namespace std;

using ll = long long;

template<typename T>
void setmin(T &x, T y) {
    x = min(x, y);
}

template<typename T>
void setmax(T &x, T y) {
    x = max(x, y);
}

#define TIME (clock() * 1.0 / CLOCKS_PER_SEC)

namespace Ment {
    template<typename T>
    T inverse(T a, T m) {
        T u = 0, v = 1;
        while (a != 0) {
            T t = m / a;
            m -= t * a;
            swap(a, m);
            u -= t * v;
            swap(u, v);
        }
        assert(m == 1);
        return u;
    }

    template<typename T>
    class Modular {
    public:
        using Type = typename decay<decltype(T::value)>::type;

        constexpr Modular() : value() {}

        template<typename U>
        Modular(const U &x) {
            value = normalize(x);
        }

        template<typename U>
        static Type normalize(const U &x) {
            Type v;
            if (-mod() <= x && x < mod()) v = static_cast<Type>(x);
            else v = static_cast<Type>(x % mod());
            if (v < 0) v += mod();
            return v;
        }

        const Type &operator()() const { return value; }

        template<typename U>
        explicit operator U() const { return static_cast<U>(value); }

        constexpr static Type mod() { return T::value; }

        Modular &operator+=(const Modular &other) {
            value += other.value - mod();
            value += (value >> 31) & mod();
            return *this;
        }

        Modular &operator-=(const Modular &other) {
            value -= other.value;
            value += (value >> 31) & mod();
            return *this;
        }

        template<typename U>
        Modular &operator+=(const U &other) { return *this += Modular(other); }

        template<typename U>
        Modular &operator-=(const U &other) { return *this -= Modular(other); }

        Modular &operator++() { return *this += 1; }

        Modular &operator--() { return *this -= 1; }

        Modular operator++(int) {
            Modular result(*this);
            *this += 1;
            return result;
        }

        Modular operator--(int) {
            Modular result(*this);
            *this -= 1;
            return result;
        }

        Modular operator-() const { return Modular(-value); }

        template<typename U = T>
        typename enable_if<is_same<typename Modular<U>::Type, int>::value, Modular>::type &
        operator*=(const Modular &rhs) {
#ifdef _WIN32
            uint64_t x = static_cast<int64_t>(value) * static_cast<int64_t>(rhs.value);
            uint32_t xh = static_cast<uint32_t>(x >> 32), xl = static_cast<uint32_t>(x), d, m;
            asm(
            "divl %4; \n\t"
            : "=a" (d), "=d" (m)
            : "d" (xh), "a" (xl), "r" (mod())
            );
            value = m;
#else
            value = normalize(static_cast<int64_t>(value) * static_cast<int64_t>(rhs.value));
#endif
            return *this;
        }

        template<typename U = T>
        typename enable_if<is_same<typename Modular<U>::Type, int64_t>::value, Modular>::type &
        operator*=(const Modular &rhs) {
            int64_t q = static_cast<int64_t>(static_cast<long double>(value) * rhs.value / mod());
            value = normalize(value * rhs.value - q * mod());
            return *this;
        }

        template<typename U = T>
        typename enable_if<!is_integral<typename Modular<U>::Type>::value, Modular>::type &
        operator*=(const Modular &rhs) {
            value = normalize(value * rhs.value);
            return *this;
        }

        Modular &operator/=(const Modular &other) { return *this *= Modular(inverse(other.value, mod())); }

        template<typename U>
        friend bool operator==(const Modular<U> &lhs, const Modular<U> &rhs);

        template<typename U>
        friend bool operator<(const Modular<U> &lhs, const Modular<U> &rhs);

        template<typename U>
        friend std::istream &operator>>(std::istream &stream, Modular<U> &number);

    private:
        Type value;
    };

    template<typename T>
    bool operator==(const Modular<T> &lhs, const Modular<T> &rhs) { return lhs.value == rhs.value; }

    template<typename T, typename U>
    bool operator==(const Modular<T> &lhs, U rhs) { return lhs == Modular<T>(rhs); }

    template<typename T, typename U>
    bool operator==(U lhs, const Modular<T> &rhs) { return Modular<T>(lhs) == rhs; }

    template<typename T>
    bool operator!=(const Modular<T> &lhs, const Modular<T> &rhs) { return !(lhs == rhs); }

    template<typename T, typename U>
    bool operator!=(const Modular<T> &lhs, U rhs) { return !(lhs == rhs); }

    template<typename T, typename U>
    bool operator!=(U lhs, const Modular<T> &rhs) { return !(lhs == rhs); }

    template<typename T>
    bool operator<(const Modular<T> &lhs, const Modular<T> &rhs) { return lhs.value < rhs.value; }

    template<typename T>
    Modular<T> operator+(const Modular<T> &lhs, const Modular<T> &rhs) { return Modular<T>(lhs) += rhs; }

    template<typename T, typename U>
    Modular<T> operator+(const Modular<T> &lhs, U rhs) { return Modular<T>(lhs) += rhs; }

    template<typename T, typename U>
    Modular<T> operator+(U lhs, const Modular<T> &rhs) { return Modular<T>(lhs) += rhs; }

    template<typename T>
    Modular<T> operator-(const Modular<T> &lhs, const Modular<T> &rhs) { return Modular<T>(lhs) -= rhs; }

    template<typename T, typename U>
    Modular<T> operator-(const Modular<T> &lhs, U rhs) { return Modular<T>(lhs) -= rhs; }

    template<typename T, typename U>
    Modular<T> operator-(U lhs, const Modular<T> &rhs) { return Modular<T>(lhs) -= rhs; }

    template<typename T>
    Modular<T> operator*(const Modular<T> &lhs, const Modular<T> &rhs) { return Modular<T>(lhs) *= rhs; }

    template<typename T, typename U>
    Modular<T> operator*(const Modular<T> &lhs, U rhs) { return Modular<T>(lhs) *= rhs; }

    template<typename T, typename U>
    Modular<T> operator*(U lhs, const Modular<T> &rhs) { return Modular<T>(lhs) *= rhs; }

    template<typename T>
    Modular<T> operator/(const Modular<T> &lhs, const Modular<T> &rhs) { return Modular<T>(lhs) /= rhs; }

    template<typename T, typename U>
    Modular<T> operator/(const Modular<T> &lhs, U rhs) { return Modular<T>(lhs) /= rhs; }

    template<typename T, typename U>
    Modular<T> operator/(U lhs, const Modular<T> &rhs) { return Modular<T>(lhs) /= rhs; }

    template<typename T, typename U>
    Modular<T> pow(const Modular<T> &a, const U &b) {
        assert(b >= 0);
        Modular<T> x = a, res = 1;
        U p = b;
        while (p > 0) {
            if (p & 1) res *= x;
            x *= x;
            p >>= 1;
        }
        return res;
    }

    template<typename T>
    string to_string(const Modular<T> &number) {
        return to_string(number());
    }

    template<typename T>
    std::ostream &operator<<(std::ostream &stream, const Modular<T> &number) {
        return stream << number();
    }

    template<typename T>
    std::istream &operator>>(std::istream &stream, Modular<T> &number) {
        typename common_type<typename Modular<T>::Type, int64_t>::type x;
        stream >> x;
        number.value = Modular<T>::normalize(x);
        return stream;
    }

    constexpr int md = 998244353;
    using Mint = Modular<std::integral_constant<decay<decltype(md)>::type, md>>;
}
//using Ment::Mint;
using namespace Ment;

// WARNING!!!!!!
// Maksim reads solution
// be careful!!!!

// solution starts here

const int maxn = 5e5 + 100;

Mint maksim[maxn];
Mint pref_maksim[maxn];

void precalc() {
    maksim[1] = 3240; // maksim
    maksim[2] = 3081; // isaf
    maksim[3] = 2841; // hudshiy
    maksim[4] = 343; // oleg
    for (int i = 5; i < maxn; i++)
        maksim[i] = maksim[i - 1] * 223 + maksim[i - 2] * 229 + maksim[i - 3] * maksim[i - 4] * 239 + 17;
    for (int i = 1; i < maxn; i++)
        pref_maksim[i] = pref_maksim[i - 1] + maksim[i];
}

ll cnt;

void solve() {
    int n, k;
    cin >> n >> k;
    Mint ans = 0;
    auto calc = [&](vector<int> &a, bool eq) {
        vector<int> st;
        vector<vector<int>> rm(n);
        for (int i = n - 1; i >= 0; i--) {
            while (!st.empty() && a[st.back()] <= a[i]) {
                rm[i].emplace_back(st.back());
                st.pop_back();
            }
            st.emplace_back(i);
        }
        vector<int> q;
        for (int i = 0; i < n; i++) {
            while (!q.empty() && a[q.back()] <= a[i])
                q.pop_back();

            st.pop_back();
            while (!rm[i].empty()) {
                st.emplace_back(rm[i].back());
                rm[i].pop_back();
            }

            {
                int L = q.empty() ? 0 : q.back() + 1;
                q.emplace_back(i);
                int l = i;
                int stpos = -1;
                {
                    int le = -1, re = st.size();
                    while (re - le > 1) {
                        int m = (le + re) / 2;
                        if (a[st[m]] > a[i] || (a[st[m]] == a[i] && eq))
                            le = m;
                        else
                            re = m;
                    }
                    stpos = le;
                }
                int bd = n - 1;
                if (stpos + 1 < st.size() && a[st[stpos + 1]] == a[i])
                    bd = st[stpos + 1] - 1;
                else if (stpos != -1)
                    bd = st[stpos] - 1;
                for (int j = stpos; j >= 0; j--)
                    if (a[st[j]] - a[i] <= k) {
                        int r = st[j];
                        int R = (j == 0 ? n - 1 : st[j - 1] - 1);
                        int t1 = 0, t2 = n - 1;
                        t1 = l;
                        t2 = r - 1;
                        t2 = min(bd, t2);
                        // following two lines is what makes it fast
                        int Y = (l + R - 1) / 2, X = (L + r) / 2;
                        setmin(t2, Y);
                        setmax(t1, X);
                        if (t1 <= t2) {
                            int le, re;
                            cnt += t2 - t1 + 1;
                            for (int m = t1; m <= t2; m++) {
                                le = max(m - l, r - m - 1) + 1;
                                re = min(m - L, R - m - 1) + 1;
                                if (le <= re) {
                                    // cerr << '[' << le << ' ' << re << "] " << a[m + !eq] << ' ' << m + !eq << ' ' << eq << '\n';
                                    ans += (pref_maksim[re] - pref_maksim[le - 1]) * (a[m + !eq] + 10);
                                }
                            }
                        }
                    } else {
                        break;
                    }
            }

        }
    };
    vector<int> a(n);
    for (int &i : a)
        cin >> i;
    calc(a, 1);
    reverse(all(a));
    calc(a, 0);
    cout << ans << '\n';
}
// check test counter

int main() {
#ifdef ONPC
    freopen("../a.in", "r", stdin);
    freopen("../a.out", "w", stdout);
#endif
    ios::sync_with_stdio(0);
    cin.tie(0);
    precalc();
    int ts;
    ts = 1;
    cin >> ts;
    for (int its = 1; its <= ts; its++)
        solve();
    cerr << '\n' << "cnt = " << cnt << '\n';
}