/**
 * 
 */

// header {{{
#include <bits/stdc++.h>
using namespace std;

using i8   = int8_t;
using u8   = uint8_t;
using i16  = int16_t;
using u16  = uint16_t;
using i32  = int32_t;
using u32  = uint32_t;
using i64  = int64_t;
using u64  = uint64_t;
#ifdef __SIZEOF_INT128__
using i128 = __int128;
using u128 = unsigned __int128;
#endif

using f32  = float;
using f64  = double;
using f80  = __float80;
using f128 = __float128;
// }}}

template<typename T> constexpr T PROCON_INF();
template<> constexpr i64 PROCON_INF<i64>() { return 1'010'000'000'000'000'000LL; }
template<> constexpr f64 PROCON_INF<f64>() { return 1e100; }

constexpr i64 INF  = PROCON_INF<i64>();
constexpr f64 FINF = PROCON_INF<f64>();

constexpr i64 MOD = 1'000'000'007LL;

constexpr f64 EPS = 1e-12;

constexpr f64 PI = 3.14159265358979323846;

// util {{{
#define FOR(i, start, end) for(i64 i = (start), i##_end=(end); i < i##_end; ++i)
#define REP(i, n) FOR(i, 0, n)

#define ALL(f,c,...) (([&](decltype((c)) cccc) { return (f)(std::begin(cccc), std::end(cccc), ## __VA_ARGS__); })(c))
#define SLICE(f,c,l,r,...) (([&](decltype((c)) cccc, decltype((l)) llll, decltype((r)) rrrr) {\
    auto iiii = llll <= rrrr ? std::begin(cccc)+llll : std::end(cccc);\
    auto jjjj = llll <= rrrr ? std::begin(cccc)+rrrr : std::end(cccc);\
    return (f)(iiii, jjjj, ## __VA_ARGS__);\
})(c,l,r))

#define GENERIC(f) ([](auto&&... args) -> decltype(auto) { return (f)(std::forward<decltype(args)>(args)...); })

template<typename F>
class FixPoint {
public:
    explicit constexpr FixPoint(F&& f) : f_(forward<F>(f)) {}

    template<typename... Args>
    constexpr decltype(auto) operator()(Args&&... args) const {
        return f_(*this, forward<Args>(args)...);
    }

private:
    const F f_;
};

template<typename F>
decltype(auto) FIX(F&& f) {
    return FixPoint<F>(forward<F>(f));
}

template<typename C>
i64 SIZE(const C& c) { return static_cast<i64>(c.size()); }

template<typename T, size_t N>
i64 SIZE(const T (&)[N]) { return static_cast<i64>(N); }

bool is_odd (i64 x) { return x % 2 != 0; }
bool is_even(i64 x) { return x % 2 == 0; }

template<typename T> i64 cmp(T x, T y) { return (y<x) - (x<y); }
template<typename T> i64 sgn(T x) { return cmp(x, T(0)); }

i64 ipow(i64 x, i64 e) {
    assert(e >= 0);
    i64 res = 1;
    REP(_, e) {
        res *= x;
    }
    return res;
}

// Haskell の divMod と同じ
pair<i64,i64> divmod(i64 a, i64 b) {
    i64 q = a / b;
    i64 r = a % b;
    if((b>0 && r<0) || (b<0 && r>0)) {
        --q;
        r += b;
    }
    return {q,r};
}

i64 div_ceil(i64 a, i64 b) {
    i64 q = a / b;
    i64 r = a % b;
    if((b>0 && r>0) || (b<0 && r<0))
        ++q;
    return q;
}

i64 div_floor(i64 a, i64 b) {
    return divmod(a,b).first;
}

i64 modulo(i64 a, i64 b) {
    return divmod(a,b).second;
}

bool feq(f64 x, f64 y, f64 eps=EPS) {
    return fabs(x-y) < eps;
}

template<typename T, typename U>
bool chmax(T& xmax, const U& x) {
    if(xmax < x) {
        xmax = x;
        return true;
    }
    return false;
}

template<typename T, typename U>
bool chmin(T& xmin, const U& x) {
    if(x < xmin) {
        xmin = x;
        return true;
    }
    return false;
}

template<typename ForwardIt, typename T, typename Comp=less<>>
ForwardIt bsearch_find(ForwardIt first, ForwardIt last, const T& x, Comp comp={}) {
    auto it = lower_bound(first, last, x, comp);
    if(it == last || comp(x,*it)) return last;
    return it;
}

// x 未満の最後の要素
template<typename BidiIt, typename T, typename Comp=less<>>
BidiIt bsearch_lt(BidiIt first, BidiIt last, const T& x, Comp comp={}) {
    auto it = lower_bound(first, last, x, comp);
    if(it == first) return last;
    return prev(it);
}

// x 以下の最後の要素
template<typename BidiIt, typename T, typename Comp=less<>>
BidiIt bsearch_le(BidiIt first, BidiIt last, const T& x, Comp comp={}) {
    auto it = upper_bound(first, last, x, comp);
    if(it == first) return last;
    return prev(it);
}

// x より大きい最初の要素
template<typename BidiIt, typename T, typename Comp=less<>>
BidiIt bsearch_gt(BidiIt first, BidiIt last, const T& x, Comp comp={}) {
    return upper_bound(first, last, x, comp);
}

// x 以上の最初の要素
template<typename BidiIt, typename T, typename Comp=less<>>
BidiIt bsearch_ge(BidiIt first, BidiIt last, const T& x, Comp comp={}) {
    return lower_bound(first, last, x, comp);
}

template<typename InputIt>
auto SUM(InputIt first, InputIt last) {
    using T = typename iterator_traits<InputIt>::value_type;
    return accumulate(first, last, T());
}

template<typename ForwardIt, typename UnaryOperation>
ForwardIt transform_self(ForwardIt first, ForwardIt last, UnaryOperation op) {
    return transform(first, last, first, op);
}

template<typename C>
void UNIQ(C& c) {
    c.erase(ALL(unique,c), end(c));
}

template<typename T, typename F>
enable_if_t<rank<T>::value==0> ARRAY_FOREACH(T& e, F f) {
    f(e);
}

template<typename Array, typename F>
enable_if_t<rank<Array>::value!=0> ARRAY_FOREACH(Array& ary, F f) {
    for(auto& e : ary)
        ARRAY_FOREACH(e, f);
}

template<typename Array, typename U>
enable_if_t<rank<Array>::value!=0> ARRAY_FILL(Array& ary, const U& v) {
    ARRAY_FOREACH(ary, [&v](auto& e) { e = v; });
}

template<typename BinaryFunc, typename UnaryFunc>
auto ON(BinaryFunc bf, UnaryFunc uf) {
    return [bf,uf](const auto& x, const auto& y) {
        return bf(uf(x), uf(y));
    };
}

template<typename F>
auto LT_ON(F f) { return ON(less<>(), f); }

template<typename F>
auto GT_ON(F f) { return ON(greater<>(), f); }

struct IDENTITY {
    template<typename T>
    constexpr T&& operator()(T&& x) const noexcept {
        return forward<T>(x);
    }
};

char digit_chr(i64 n) {
    return static_cast<char>('0' + n);
}

i64 digit_ord(char c) {
    return c - '0';
}

char lower_chr(i64 n) {
    return static_cast<char>('a' + n);
}

i64 lower_ord(char c) {
    return c - 'a';
}

char upper_chr(i64 n) {
    return static_cast<char>('A' + n);
}

i64 upper_ord(char c) {
    return c - 'A';
}

// 出力は operator<< を直接使わず、このテンプレート経由で行う
// 提出用出力とデバッグ用出力を分けるため
template<typename T>
struct Formatter {
    static ostream& write_str(ostream& out, const T& x)  { return out << x; }
    static ostream& write_repr(ostream& out, const T& x) { return out << x; }
};

template<typename T>
ostream& WRITE_STR(ostream& out, const T& x) {
    return Formatter<T>::write_str(out, x);
}

template<typename T>
ostream& WRITE_REPR(ostream& out, const T& x) {
    return Formatter<T>::write_repr(out, x);
}

template<typename InputIt>
ostream& WRITE_JOIN_STR(ostream& out, InputIt first, InputIt last, const string& sep) {
    while(first != last) {
        WRITE_STR(out, *first++);
        if(first != last)
            out << sep;
    }
    return out;
}

template<typename InputIt>
ostream& WRITE_JOIN_REPR(ostream& out, InputIt first, InputIt last, const string& sep) {
    while(first != last) {
        WRITE_REPR(out, *first++);
        if(first != last)
            out << sep;
    }
    return out;
}

template<typename InputIt>
ostream& WRITE_RANGE_STR(ostream& out, InputIt first, InputIt last) {
    return WRITE_JOIN_STR(out, first, last, " ");
}

template<typename InputIt>
ostream& WRITE_RANGE_REPR(ostream& out, InputIt first, InputIt last) {
    out << "[";
    WRITE_JOIN_REPR(out, first, last, ", ");
    out << "]";
    return out;
}

template<typename T>
void FROM_STR(const string& s, T& x) {
    istringstream in(s);
    in >> x;
}

template<typename T>
string TO_STR(const T& x) {
    ostringstream out;
    WRITE_STR(out, x);
    return out.str();
}

template<typename T>
string TO_REPR(const T& x) {
    ostringstream out;
    WRITE_REPR(out, x);
    return out.str();
}

template<typename InputIt>
string RANGE_TO_STR(InputIt first, InputIt last) {
    ostringstream out;
    WRITE_RANGE_STR(out, first, last);
    return out.str();
}

template<typename InputIt>
string RANGE_TO_REPR(InputIt first, InputIt last) {
    ostringstream out;
    WRITE_RANGE_REPR(out, first, last);
    return out.str();
}

template<typename InputIt>
string JOIN(InputIt first, InputIt last, const string& sep) {
    ostringstream out;
    WRITE_JOIN_STR(out, first, last, sep);
    return out.str();
}

template<>
struct Formatter<i64> {
    static ostream& write_str(ostream& out, i64 x) {
        return out << x;
    }
    static ostream& write_repr(ostream& out, i64 x) {
        if(x == INF) return out << "INF";
        if(x == -INF) return out << "-INF";
        return out << x;
    }
};

template<>
struct Formatter<f64> {
    static ostream& write_str(ostream& out, f64 x) {
        return out << x;
    }
    static ostream& write_repr(ostream& out, f64 x) {
#pragma GCC diagnostic push
#pragma GCC diagnostic ignored "-Wfloat-equal"
        if(x == FINF) return out << "FINF";
        if(x == -FINF) return out << "-FINF";
#pragma GCC diagnostic pop
        return out << x;
    }
};

template<typename T>
struct Formatter<vector<T>> {
    static ostream& write_str(ostream& out, const vector<T>& v) {
        return WRITE_RANGE_STR(out, begin(v), end(v));
    }
    static ostream& write_repr(ostream& out, const vector<T>& v) {
        out << "vector";
        return WRITE_RANGE_REPR(out, begin(v), end(v));
    }
};

template<typename T1, typename T2>
struct Formatter<pair<T1,T2>> {
    static ostream& write_str(ostream& out, const pair<T1,T2>& p) {
        WRITE_STR(out, p.first);
        out << ' ';
        WRITE_STR(out, p.second);
        return out;
    }
    static ostream& write_repr(ostream& out, const pair<T1,T2>& p) {
        out << "(";
        WRITE_REPR(out, p.first);
        out << ",";
        WRITE_REPR(out, p.second);
        out << ")";
        return out;
    }
};

template<typename... TS>
struct Formatter<tuple<TS...>> {
    template<size_t I=0, enable_if_t<I == sizeof...(TS), nullptr_t> = nullptr>
    static ostream& write_str_impl(ostream& out, const tuple<TS...>&) {
        return out;
    }
    template<size_t I=0, enable_if_t<I < sizeof...(TS), nullptr_t> = nullptr>
    static ostream& write_str_impl(ostream& out, const tuple<TS...>& t) {
        if(I != 0) out << ' ';
        WRITE_STR(out, get<I>(t));
        return write_str_impl<I+1>(out, t);
    }

    template<size_t I=0, enable_if_t<I == sizeof...(TS), nullptr_t> = nullptr>
    static ostream& write_repr_impl(ostream& out, const tuple<TS...>&) {
        if(sizeof...(TS) == 0) out << "(";
        return out << ")";
    }
    template<size_t I=0, enable_if_t<I < sizeof...(TS), nullptr_t> = nullptr>
    static ostream& write_repr_impl(ostream& out, const tuple<TS...>& t) {
        if(I == 0)
            out << "(";
        else
            out << ",";
        WRITE_REPR(out, get<I>(t));
        return write_repr_impl<I+1>(out, t);
    }

    static ostream& write_str(ostream& out, const tuple<TS...>& t) {
        return write_str_impl(out, t);
    }
    static ostream& write_repr(ostream& out, const tuple<TS...>& t) {
        return write_repr_impl(out, t);
    }
};

template<typename T>
void RD(T& x) {
    cin >> x;
#ifdef PROCON_LOCAL
    assert(cin);
#endif
}

template<typename T>
void RD(vector<T>& v, i64 n) {
    v.reserve(n);
    REP(_, n) {
        T e; RD(e);
        v.emplace_back(e);
    }
}

void PRINT() {}

template<typename T, typename... TS>
void PRINT(const T& x, const TS& ...args) {
    WRITE_STR(cout, x);
    if(sizeof...(args)) {
        cout << ' ';
        PRINT(args...);
    }
}

template<typename... TS>
void PRINTLN(const TS& ...args) {
    PRINT(args...);
    cout << '\n';
}

[[noreturn]] void EXIT() {
#ifdef PROCON_LOCAL
    cerr.flush();
#endif
    cout.flush();
    _Exit(0);
}

template<typename T>
void DBG_IMPL(i64 line, const char* expr, const T& value) {
#ifdef PROCON_LOCAL
    cerr << "[L " << line << "]: ";
    cerr << expr << " = ";
    WRITE_REPR(cerr, value);
    cerr << "\n";
#endif
}

template<typename T, size_t N>
void DBG_ARRAY_IMPL(i64 line, const char* expr, const T (&ary)[N]) {
#ifdef PROCON_LOCAL
    cerr << "[L " << line << "]: ";
    cerr << expr << " = ";
    WRITE_RANGE_REPR(cerr, begin(ary), end(ary));
    cerr << "\n";
#endif
}

template<typename InputIt>
void DBG_RANGE_IMPL(i64 line, const char* expr1, const char* expr2, InputIt first, InputIt last) {
#ifdef PROCON_LOCAL
    cerr << "[L " << line << "]: ";
    cerr << expr1 << "," << expr2 << " = ";
    WRITE_RANGE_REPR(cerr, first, last);
    cerr << "\n";
#endif
}

#define DBG(expr) DBG_IMPL(__LINE__, #expr, (expr))
#define DBG_ARRAY(expr) DBG_ARRAY_IMPL(__LINE__, #expr, (expr))
#define DBG_RANGE(first,last) DBG_RANGE_IMPL(__LINE__, #first, #last, (first), (last))

#define PAIR  make_pair
#define TUPLE make_tuple
// }}}

// init {{{
struct ProconInit {
    static constexpr int IOS_PREC = 15;
    static constexpr bool AUTOFLUSH = false;

    ProconInit() {
        cin.tie(nullptr);
        ios::sync_with_stdio(false);
        cout << fixed << setprecision(IOS_PREC);
#ifdef PROCON_LOCAL
        cerr << fixed << setprecision(IOS_PREC);
#endif
        if(AUTOFLUSH)
            cout << unitbuf;
    }
} PROCON_INIT;
// }}}

// num {{{

// 事前条件: a >= 0, b >= 0
i64 gcd_impl(i64 a, i64 b) {
    if(b == 0) return a;
    return gcd_impl(b, a%b);
}

// gcd(0,0) = 0
i64 gcd(i64 a, i64 b) {
    return gcd_impl(abs(a), abs(b));
}

// lcm(0,x) は未定義
i64 lcm(i64 a, i64 b) {
    assert(a != 0 && b != 0);
    a = abs(a);
    b = abs(b);
    return a / gcd_impl(a,b) * b;
}

// 事前条件: a >= 0, b >= 0
i64 extgcd_impl(i64 a, i64 b, i64& x, i64& y) {
    if(b == 0) {
        x = 1; y = 0;
        return a;
    }
    i64 g = extgcd_impl(b, a%b, y, x);
    y -= a/b * x;
    return g;
}

// g=gcd(a,b), および ax+by=g の整数解 (x0,y0) を求める
// (g,x0,y0) を返す
// g!=0 のとき、一般解は (x,y) = (x0+m*b/g, y0-m*a/g) で与えられる(mは整数)
tuple<i64,i64,i64> extgcd(i64 a, i64 b) {
    i64 x, y;
    i64 g = extgcd_impl(abs(a), abs(b), x, y);
    x *= sgn(a);
    y *= sgn(b);
    return make_tuple(g, x, y);
}

// 素因数分解
// (素因数,指数) のリストを返す
// n >= 1 でなければならない
// n == 1 の場合、空リストを返す
vector<pair<i64,i64>> factorize(i64 n) {
    assert(n >= 1);

    vector<pair<i64,i64>> res;

    i64 m = n;
    for(i64 i = 2; i*i <= n; ++i) {
        if(m == 1) break;
        i64 e = 0;
        while(m % i == 0) {
            ++e;
            m /= i;
        }
        if(e) res.emplace_back(i, e);
    }
    if(m > 1) res.emplace_back(m, 1);

    return res;
}

// Miller-Rabin 法
//
// 参考: http://miller-rabin.appspot.com/
bool is_prime_u32(u32 n) {
    static constexpr u32 AS[] {
         2,
         7,
        61,
    };

    static const auto mulmod32 = [](u32 a, u32 b, u32 m) -> u32 {
        u64 res = a;
        res *= b;
        res %= m;
        return static_cast<u32>(res);
    };

    static const auto powmod32 = [](u32 a, u32 b, u32 m) -> u32 {
        u32 res = 1;
        while(b > 0) {
            if(b & 1)
                res = mulmod32(res, a, m);
            a = mulmod32(a, a, m);
            b >>= 1;
        }
        return res;
    };

    if(n <= 1)     return false;
    if(n == 2)     return true;
    if(n % 2 == 0) return false;

    u32 d = n-1;
    u32 s = __builtin_ctz(d);
    d >>= s;

    for(u32 a : AS) {
        if(a >= n) a %= n;
        if(a == 0) continue;

        u32 x = powmod32(a, d, n);
        if(x == 1 || x == n-1) continue;

        u32 r;
        for(r = 1; r < s; ++r) {
            x = mulmod32(x, x, n);
            if(x == 1)   return false;
            if(x == n-1) break;
        }
        if(r == s) return false;
    }

    return true;
}

bool is_prime_u64(u64 n) {
    static constexpr u64 AS[] {
                 2,
               325,
              9375,
             28178,
            450775,
           9780504,
        1795265022,
    };

    static const auto mulmod64 = [](u64 a, u64 b, u64 m) -> u64 {
        u128 res = a;
        res *= b;
        res %= m;
        return static_cast<u64>(res);
    };

    static const auto powmod64 = [](u64 a, u64 b, u64 m) -> u64 {
        u64 res = 1;
        while(b > 0) {
            if(b & 1)
                res = mulmod64(res, a, m);
            a = mulmod64(a, a, m);
            b >>= 1;
        }
        return res;
    };

    if(n <= numeric_limits<u32>::max()) return is_prime_u32(static_cast<u32>(n));
    if(n % 2 == 0) return false;

    u64 d = n-1;
    u64 s = __builtin_ctzll(d);
    d >>= s;

    for(u64 a : AS) {
        if(a >= n) a %= n;
        if(a == 0) continue;

        u64 x = powmod64(a, d, n);
        if(x == 1 || x == n-1) continue;

        u64 r;
        for(r = 1; r < s; ++r) {
            x = mulmod64(x, x, n);
            if(x == 1)   return false;
            if(x == n-1) break;
        }
        if(r == s) return false;
    }

    return true;
}

// 二分累乗
template<typename Monoid>
Monoid pow_binary(Monoid x, i64 e) {
    assert(e >= 0);

    Monoid res(1);  // 行列などの場合はここを適当に変える
    Monoid cur = x;
    while(e > 0) {
        if(e & 1)
            res *= cur;
        cur *= cur;
        e >>= 1;
    }
    return res;
}

// mod m での a の逆元
// a ⊥ m でなければならない
i64 inv_mod(i64 a, i64 m) {
    i64 g,x0; tie(g,x0,ignore) = extgcd(a, m);
    assert(g == 1);
    return modulo(x0, m);
}

template<i64 P>
struct ModPT {
    static_assert(P >= 2, "P must be a prime");
    i64 v_;  // [0,P)

    ModPT() : v_(0) {}
    ModPT(i64 v) : v_(modulo(v,P)) {}

    ModPT operator-() const {
        return ModPT(-v_);
    }
    ModPT& operator+=(ModPT rhs) {
        v_ += rhs.v_;
        v_ %= P;
        return *this;
    }
    ModPT& operator-=(ModPT rhs) {
        v_ += P;
        v_ -= rhs.v_;
        v_ %= P;
        return *this;
    }
    ModPT& operator*=(ModPT rhs) {
        v_ *= rhs.v_;
        v_ %= P;
        return *this;
    }

    ModPT& operator++() {
        return *this += 1;
    }
    ModPT& operator--() {
        return *this -= 1;
    }
    ModPT operator++(int) {
        ModPT res(*this);
        ++*this;
        return res;
    }
    ModPT operator--(int) {
        ModPT res(*this);
        --*this;
        return res;
    }

    ModPT inv() const {
        return ModPT(inv_mod(v_,P));
    }
};

template<i64 P>
ModPT<P> operator+(ModPT<P> lhs, ModPT<P> rhs) { return ModPT<P>(lhs) += rhs; }
template<i64 P>
ModPT<P> operator+(ModPT<P> lhs, i64 rhs) { return ModPT<P>(lhs) += rhs; }
template<i64 P>
ModPT<P> operator+(i64 lhs, ModPT<P> rhs) { return ModPT<P>(rhs) += lhs; }
template<i64 P>
ModPT<P> operator-(ModPT<P> lhs, ModPT<P> rhs) { return ModPT<P>(lhs) -= rhs; }
template<i64 P>
ModPT<P> operator-(ModPT<P> lhs, i64 rhs) { return ModPT<P>(lhs) -= rhs; }
template<i64 P>
ModPT<P> operator-(i64 lhs, ModPT<P> rhs) { return ModPT<P>(rhs) -= lhs; }
template<i64 P>
ModPT<P> operator*(ModPT<P> lhs, ModPT<P> rhs) { return ModPT<P>(lhs) *= rhs; }
template<i64 P>
ModPT<P> operator*(ModPT<P> lhs, i64 rhs) { return ModPT<P>(lhs) *= rhs; }
template<i64 P>
ModPT<P> operator*(i64 lhs, ModPT<P> rhs) { return ModPT<P>(rhs) *= lhs; }

template<i64 P>
bool operator==(ModPT<P> lhs, ModPT<P> rhs) { return lhs.v_ == rhs.v_; }
template<i64 P>
bool operator==(ModPT<P> lhs, i64 rhs) { return lhs == ModPT<P>(rhs); }
template<i64 P>
bool operator==(i64 lhs, ModPT<P> rhs) { return ModPT<P>(lhs) == rhs; }
template<i64 P>
bool operator!=(ModPT<P> lhs, ModPT<P> rhs) { return !(lhs == rhs); }
template<i64 P>
bool operator!=(ModPT<P> lhs, i64 rhs) { return !(lhs == rhs); }
template<i64 P>
bool operator!=(i64 lhs, ModPT<P> rhs) { return !(lhs == rhs); }

template<i64 P>
istream& operator>>(istream& in, ModPT<P>& x) {
    return in >> x.v_;
}

template<i64 P>
struct Formatter<ModPT<P>> {
    static ostream& write_str(ostream& out, ModPT<P> x) {
        return WRITE_STR(out, x.v_);
    }
    static ostream& write_repr(ostream& out, ModPT<P> x) {
        return WRITE_REPR(out, x.v_);
    }
};

using ModP = ModPT<MOD>;

// エラトステネスのふるい
template<i64 N>
bool (&is_prime_table())[N] {
    static_assert(N >= 3, "");
    static bool prime[N] {};

    if(!prime[2]) {
        fill(begin(prime)+2, end(prime), true);
        for(i64 i = 2; i*i <= N-1; ++i) {
            if(!prime[i]) continue;
            for(i64 j = i+i; j < N; j += i)
                prime[j] = false;
        }
    }
    return prime;
}

// F(0) = 0
// F(1) = 1
// F(n) = F(n-1) + F(n-2)
//
// // decltype(auto) で受けると SIZE() が使える (auto だとポインタになってしまう)
// decltype(auto) fib = fibonacci_table<1000>();
template<i64 N>
ModP (&fibonacci_table())[N] {
    static_assert(N >= 2, "");
    static ModP fib[N] {};

    if(fib[1] != 1) {
        fib[0] = 0;
        fib[1] = 1;
        FOR(i, 2, N) {
            fib[i] = fib[i-1] + fib[i-2];
        }
    }
    return fib;
}

template<i64 N>
ModP (&factorial_table())[N] {
    static_assert(N >= 1, "");
    static ModP fac[N] {};

    if(fac[0] != 1) {
        fac[0] = 1;
        FOR(i, 1, N) {
            fac[i] = i * fac[i-1];
        }
    }
    return fac;
}

template<i64 N>
ModP (&ifactorial_table())[N] {
    static_assert(N >= 1, "");
    static ModP ifac[N] {};

    if(ifac[0] != 1) {
        decltype(auto) fac = factorial_table<N>();
        ifac[N-1] = fac[N-1].inv();
        for(i64 i = N-2; i >= 0; --i) {
            ifac[i] = (i+1) * ifac[i+1];
        }
    }
    return ifac;
}

ModP permutation_count_fac(i64 n, i64 r, const ModP* fac, const ModP* ifac) {
    if(n < r) return 0;
    return fac[n] * ifac[n-r];
}

template<i64 H, i64 W>
ModP (&combination_count_table())[H][W] {
    static_assert(W >= 1 && H >= W, "");
    static ModP dp[H][W] {};

    if(dp[0][0] != 1) {
        REP(i, H) {
            dp[i][0] = 1;
            dp[i][i] = 1;
        }
        FOR(i, 1, H) FOR(j, 1, i) {
            dp[i][j] = dp[i-1][j-1] + dp[i-1][j];
        }
    }
    return dp;
}

template<i64 H, i64 W>
auto combination_count_func() {
    static_assert(W >= 1 && H >= W, "");
    auto f = FIX([](auto self, i64 n, i64 r) -> ModP {
        static bool done[H][W] {};
        static ModP memo[H][W];

        if(n <  r) return 0;
        if(r == 0) return 1;
        if(n == r) return 1;

        if(!done[n][r]) {
            ModP res = self(n-1,r-1) + self(n-1,r);

            memo[n][r] = res;
            done[n][r] = true;
        }
        return memo[n][r];
    });
    return f;
}

ModP combination_count_fac(i64 n, i64 r, const ModP* fac, const ModP* ifac) {
    if(n < r) return 0;
    return fac[n] * ifac[r] * ifac[n-r];
}

// 分割数 P(n,k) (n を k 個の正整数の和で表す場合の数)
//
// 「n を 最大値 k の正整数の和で表す場合の数」でもある。
// 「n を k 個『以下』の正整数の和で表す場合の数」は sum(P(n,i)) (1<=i<=k)
// 「n を k 個の『非負整数』の和で表す場合の数」は P(n+k,k)
//
// P(0,0) = 1
// P(n,0) = 0
// P(0,k) = 0
// n < k のとき P(n,k) = 0
// P(n,1) = 1
// P(n,n) = 1
template<i64 H, i64 W>
ModP (&partition_count_table())[H][W] {
    static_assert(W >= 1 && H >= W, "");
    static ModP dp[H][W] {};

    if(dp[0][0] != 1) {
        REP(j, W) {
            dp[j][j] = 1;
        }
        FOR(i, 2, H) {
            dp[i][1] = 1;
        }
        FOR(i, 3, H) {
            FOR(j, 2, min<i64>(i,W)) {
                dp[i][j] = dp[i-1][j-1] + dp[i-j][j];
            }
        }
    }
    return dp;
}

// 分割数 メモ化再帰版
template<i64 H, i64 W>
auto partition_count_func() {
    static_assert(W >= 1 && H >= W, "");
    auto f = FIX([](auto self, i64 n, i64 k) -> ModP {
        static bool done[H][W] {};
        static ModP memo[H][W];

        if(n <  k) return 0;
        if(n == k) return 1;
        if(k == 1) return 1;

        if(!done[n][k]) {
            ModP res = self(n-1,k-1) + self(n-k,k);

            memo[n][k] = res;
            done[n][k] = true;
        }
        return memo[n][k];
    });
    return f;
}

// }}}

// cum (build() 忘れに注意) {{{

// 1次元累積和
template<typename T>
struct Cum1 {
    vector<T> v_;

    explicit Cum1(i64 n) : v_(n+1, T(0)) {}

    void add(i64 i, T val) {
        v_[i+1] += val;
    }

    void build() {
        ALL(partial_sum, v_, begin(v_));
    }

    T query(i64 i, i64 n) const {
        return v_[i+n] - v_[i];
    }
};

// 2次元累積和
template<typename T>
struct Cum2 {
    vector<vector<T>> v_;

    Cum2(i64 h, i64 w) : v_(h+1, vector<T>(w+1, T(0))) {}

    void add(i64 y, i64 x, T val) {
        v_[y+1][x+1] += val;
    }

    void build() {
        i64 h = SIZE(v_) - 1;
        FOR(y, 1, h+1) {
            ALL(partial_sum, v_[y], begin(v_[y]));
            ALL(transform, v_[y-1], begin(v_[y]), begin(v_[y]), plus<>());
        }
    }

    T query(i64 y, i64 x, i64 h, i64 w) const {
        return v_[y+h][x+w] - v_[y+h][x] - v_[y][x+w] + v_[y][x];
    }
};

// }}}

//--------------------------------------------------------------------

bool is_prime(i64 n) {
    assert(n >= 0);
    return is_prime_u64(static_cast<u64>(n));
}

bool is_ok(i64 n) {
    if(is_even(n)) return false;
    return is_prime(n) && is_prime((n+1)/2);
}

void solve() {
    Cum1<i64> cum(100001);
    REP(i, 100001) {
        if(is_ok(i))
            cum.add(i, 1);
    }
    cum.build();

    i64 Q; RD(Q);
    REP(_, Q) {
        i64 l,r; RD(l); RD(r);
        i64 n = r - l + 1;
        i64 ans = cum.query(l, n);
        PRINTLN(ans);
    }
}

signed main() {
    

    solve();

    EXIT();
}


Measured memory_bytes: 1408