結果

問題 No.3101 Range Eratosthenes Query
ユーザー kk2a
提出日時 2025-04-11 23:17:34
言語 C++23
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 255 ms / 3,000 ms
コード長 27,270 bytes
コンパイル時間 2,102 ms
コンパイル使用メモリ 154,032 KB
実行使用メモリ 28,564 KB
最終ジャッジ日時 2025-04-11 23:17:55
合計ジャッジ時間 8,472 ms
ジャッジサーバーID
(参考情報)
judge2 / judge5
このコードへのチャレンジ
(要ログイン)
ファイルパターン 結果
sample AC * 2
other AC * 24
権限があれば一括ダウンロードができます

ソースコード

diff #

#include <deque>
#include <cassert>
#include <array>
#include <set>
#include <iterator>
#include <bitset>
#include <functional>
#include <unordered_map>
#include <string>
#include <utility>
#include <vector>
#include <queue>
#include <iomanip>
#include <istream>
#include <type_traits>
#include <numeric>
#include <algorithm>
#include <fstream>
#include <unordered_set>
#include <ostream>
#include <stack>
#include <map>
#include <iostream>
#include <optional>

#ifndef KK2_TEMPLATE_PROCON_HPP
#define KK2_TEMPLATE_PROCON_HPP 1


#ifndef KK2_TEMPLATE_CONSTANT_HPP
#define KK2_TEMPLATE_CONSTANT_HPP 1

#ifndef KK2_TEMPLATE_TYPE_ALIAS_HPP
#define KK2_TEMPLATE_TYPE_ALIAS_HPP 1


using u32 = unsigned int;
using i64 = long long;
using u64 = unsigned long long;
using i128 = __int128_t;
using u128 = __uint128_t;

using pi = std::pair<int, int>;
using pl = std::pair<i64, i64>;
using pil = std::pair<int, i64>;
using pli = std::pair<i64, int>;

template <class T> using vc = std::vector<T>;
template <class T> using vvc = std::vector<vc<T>>;
template <class T> using vvvc = std::vector<vvc<T>>;
template <class T> using vvvvc = std::vector<vvvc<T>>;

template <class T> using pq = std::priority_queue<T>;
template <class T> using pqi = std::priority_queue<T, std::vector<T>, std::greater<T>>;

#endif // KK2_TEMPLATE_TYPE_ALIAS_HPP

template <class T> constexpr T infty = 0;
template <> constexpr int infty<int> = (1 << 30) - 123;
template <> constexpr i64 infty<i64> = (1ll << 62) - (1ll << 31);
template <> constexpr i128 infty<i128> = (i128(1) << 126) - (i128(1) << 63);
template <> constexpr u32 infty<u32> = infty<int>;
template <> constexpr u64 infty<u64> = infty<i64>;
template <> constexpr u128 infty<u128> = infty<i128>;
template <> constexpr double infty<double> = infty<i64>;
template <> constexpr long double infty<long double> = infty<i64>;

constexpr int mod = 998244353;
constexpr int modu = 1e9 + 7;
constexpr long double PI = 3.14159265358979323846;

#endif // KK2_TEMPLATE_CONSTANT_HPP
#ifndef KK2_TEMPLATE_FUNCTION_UTIL_HPP
#define KK2_TEMPLATE_FUNCTION_UTIL_HPP 1


#ifndef KK2_MATH_MONOID_MAX_HPP
#define KK2_MATH_MONOID_MAX_HPP 1


#ifndef KK2_TYPE_TRAITS_IO_HPP
#define KK2_TYPE_TRAITS_IO_HPP 1



namespace kk2 {

namespace type_traits {

struct istream_tag {};
struct ostream_tag {};

} // namespace type_traits

template <typename T> using is_standard_istream =
    typename std::conditional<std::is_same<T, std::istream>::value
                                  || std::is_same<T, std::ifstream>::value,
                              std::true_type,
                              std::false_type>::type;
template <typename T> using is_standard_ostream =
    typename std::conditional<std::is_same<T, std::ostream>::value
                                  || std::is_same<T, std::ofstream>::value,
                              std::true_type,
                              std::false_type>::type;
template <typename T> using is_user_defined_istream = std::is_base_of<type_traits::istream_tag, T>;
template <typename T> using is_user_defined_ostream = std::is_base_of<type_traits::ostream_tag, T>;

template <typename T> using is_istream =
    typename std::conditional<is_standard_istream<T>::value || is_user_defined_istream<T>::value,
                              std::true_type,
                              std::false_type>::type;

template <typename T> using is_ostream =
    typename std::conditional<is_standard_ostream<T>::value || is_user_defined_ostream<T>::value,
                              std::true_type,
                              std::false_type>::type;

template <typename T> using is_istream_t = std::enable_if_t<is_istream<T>::value>;
template <typename T> using is_ostream_t = std::enable_if_t<is_ostream<T>::value>;

} // namespace kk2

#endif // KK2_TYPE_TRAITS_IO_HPP

namespace kk2 {

namespace monoid {

template <class S, class Compare = std::less<S>> struct Max {
    static constexpr bool commutative = true;
    using M = Max;
    S a;
    bool is_unit;

    Max() : a(S()), is_unit(true) {}
    Max(S a_) : a(a_), is_unit(false) {}
    operator S() const { return a; }

    inline static M op(M l, M r) {
        if (l.is_unit or r.is_unit) return l.is_unit ? r : l;
        return Compare{}(l.a, r.a) ? r : l;
    }

    inline static M unit() { return M(); }

    bool operator==(const M &rhs) const {
        return is_unit == rhs.is_unit and (is_unit or a == rhs.a);
    }

    bool operator!=(const M &rhs) const {
        return is_unit != rhs.is_unit or (!is_unit and a != rhs.a);
    }

    template <class OStream, is_ostream_t<OStream> * = nullptr>
    friend OStream &operator<<(OStream &os, const M &x) {
        if (x.is_unit) os << "-inf";
        else os << x.a;
        return os;
    }

    template <class IStream, is_istream_t<IStream> * = nullptr>
    friend IStream &operator>>(IStream &is, M &x) {
        is >> x.a;
        x.is_unit = false;
        return is;
    }
};

} // namespace monoid

} // namespace kk2

#endif // MATH_MONOID_MAX_HPP
#ifndef KK2_MATH_MONOID_MIN_HPP
#define KK2_MATH_MONOID_MIN_HPP 1



namespace kk2 {

namespace monoid {

template <class S, class Compare = std::less<S>> struct Min {
    static constexpr bool commutative = true;
    using M = Min;
    S a;
    bool is_unit;

    Min() : a(S()), is_unit(true) {}
    Min(S a_) : a(a_), is_unit(false) {}
    operator S() const { return a; }

    inline static M op(M l, M r) {
        if (l.is_unit or r.is_unit) return l.is_unit ? r : l;
        return Compare{}(l.a, r.a) ? l : r;
    }

    inline static M unit() { return M(); }

    bool operator==(const M &rhs) const {
        return is_unit == rhs.is_unit and (is_unit or a == rhs.a);
    }

    bool operator!=(const M &rhs) const {
        return is_unit != rhs.is_unit or (!is_unit and a != rhs.a);
    }

    template <class OStream, is_ostream_t<OStream> * = nullptr>
    friend OStream &operator<<(OStream &os, const M &x) {
        if (x.is_unit) os << "inf";
        else os << x.a;
        return os;
    }

    template <class IStream, is_istream_t<IStream> * = nullptr>
    friend IStream &operator>>(IStream &is, M &x) {
        is >> x.a;
        x.is_unit = false;
        return is;
    }
};

} // namespace monoid

} // namespace kk2

#endif // KK2_MATH_MONOID_MIN_HPP
#ifndef KK2_TYPE_TRAITS_CONTAINER_TRAITS_HPP
#define KK2_TYPE_TRAITS_CONTAINER_TRAITS_HPP 1



namespace kk2 {

template <typename T> struct is_vector : std::false_type {};
template <typename T, typename Alloc> struct is_vector<std::vector<T, Alloc>> : std::true_type {};

} // namespace kk2

#endif // KK2_TYPE_TRAITS_CONTAINER_TRAITS_HPP

namespace kk2 {

template <class T, class... Sizes> auto make_vector(int first, Sizes... sizes) {
    if constexpr (sizeof...(sizes) == 0) {
        return std::vector<T>(first);
    } else {
        return std::vector<decltype(make_vector<T>(sizes...))>(first, make_vector<T>(sizes...));
    }
}

template <class T, class U> void fill_all(std::vector<T> &v, const U &x) {
    if constexpr (is_vector<T>::value) {
        for (auto &u : v) fill_all(u, x);
    } else {
        std::fill(v.begin(), v.end(), T(x));
    }
}

template <class T, class U> int iota_all(std::vector<T> &v, U x, int offset = 0) {
    if constexpr (is_vector<T>::value) {
        for (auto &u : v) offset += iota_all(u, x + offset);
    } else {
        for (auto &u : v) u = x++, ++offset;
    }
    return offset;
}

template <class C> int mysize(const C &c) { return size(c); }


// T: commutative monoid, F: (U, T) -> U
template <class U, class T, class F>
U all_monoid_prod(const std::vector<T> &v, U unit, const F &f) {
    U res = unit;
    if constexpr (is_vector<T>::value) {
        for (const auto &x : v) res = f(res, all_monoid_prod(x, unit, f));
    } else {
        for (const auto &x : v) res = f(res, x);
    }
    return res;
}

template <class U, class T> U all_sum(const std::vector<T> &v, U unit = U()) {
    return all_monoid_prod<U, T>(v, unit, [](U a, U b) { return a + b; });
}
template <class U, class T> U all_prod(const std::vector<T> &v, U unit = U(1)) {
    return all_monoid_prod<U, T>(v, unit, [](U a, U b) { return a * b; });
}
template <class U, class T> U all_xor(const std::vector<T> &v, U unit = U()) {
    return all_monoid_prod<U, T>(v, unit, [](U a, U b) { return a ^ b; });
}
template <class U, class T> U all_and(const std::vector<T> &v, U unit = U(-1)) {
    return all_monoid_prod<U, T>(v, unit, [](U a, U b) { return a & b; });
}
template <class U, class T> U all_or(const std::vector<T> &v, U unit = U()) {
    return all_monoid_prod<U, T>(v, unit, [](U a, U b) { return a | b; });
}
template <class U, class T> U all_min(const std::vector<T> &v) {
    return all_monoid_prod<monoid::Min<U>, T>(v, monoid::Min<U>::unit(), monoid::Min<U>::op);
}
template <class U, class T> U all_max(const std::vector<T> &v) {
    return all_monoid_prod<monoid::Max<U>, T>(v, monoid::Max<U>::unit(), monoid::Max<U>::op);
}
template <class U, class T> U all_gcd(const std::vector<T> &v, U unit = U()) {
    return all_monoid_prod<U, T>(v, unit, [](U a, U b) { return std::gcd(a, b); });
}
template <class U, class T> U all_lcm(const std::vector<T> &v, U unit = U(1)) {
    return all_monoid_prod<U, T>(v, unit, [](U a, U b) { return std::lcm(a, b); });
}

} // namespace kk2

#endif // KK2_TEMPLATE_FUNCTION_UTIL_HPP
#ifndef KK2_TEMPLATE_IO_UTIL_HPP
#define KK2_TEMPLATE_IO_UTIL_HPP 1



// なんかoj verifyはプロトタイプ宣言が落ちる

namespace impl {

struct read {
    template <class IStream, class T> inline static void all_read(IStream &is, T &x) { is >> x; }

    template <class IStream, class T, class U>
    inline static void all_read(IStream &is, std::pair<T, U> &p) {
        all_read(is, p.first);
        all_read(is, p.second);
    }

    template <class IStream, class T> inline static void all_read(IStream &is, std::vector<T> &v) {
        for (T &x : v) all_read(is, x);
    }

    template <class IStream, class T, size_t F>
    inline static void all_read(IStream &is, std::array<T, F> &a) {
        for (T &x : a) all_read(is, x);
    }
};

struct write {
    template <class OStream, class T> inline static void all_write(OStream &os, const T &x) {
        os << x;
    }

    template <class OStream, class T, class U>
    inline static void all_write(OStream &os, const std::pair<T, U> &p) {
        all_write(os, p.first);
        all_write(os, ' ');
        all_write(os, p.second);
    }

    template <class OStream, class T>
    inline static void all_write(OStream &os, const std::vector<T> &v) {
        for (int i = 0; i < (int)v.size(); ++i) {
            if (i) all_write(os, ' ');
            all_write(os, v[i]);
        }
    }

    template <class OStream, class T, size_t F>
    inline static void all_write(OStream &os, const std::array<T, F> &a) {
        for (int i = 0; i < (int)F; ++i) {
            if (i) all_write(os, ' ');
            all_write(os, a[i]);
        }
    }
};

} // namespace impl

template <class IStream, class T, class U, kk2::is_istream_t<IStream> * = nullptr>
IStream &operator>>(IStream &is, std::pair<T, U> &p) {
    impl::read::all_read(is, p);
    return is;
}

template <class IStream, class T, kk2::is_istream_t<IStream> * = nullptr>
IStream &operator>>(IStream &is, std::vector<T> &v) {
    impl::read::all_read(is, v);
    return is;
}

template <class IStream, class T, size_t F, kk2::is_istream_t<IStream> * = nullptr>
IStream &operator>>(IStream &is, std::array<T, F> &a) {
    impl::read::all_read(is, a);
    return is;
}

template <class OStream, class T, class U, kk2::is_ostream_t<OStream> * = nullptr>
OStream &operator<<(OStream &os, const std::pair<T, U> &p) {
    impl::write::all_write(os, p);
    return os;
}

template <class OStream, class T, kk2::is_ostream_t<OStream> * = nullptr>
OStream &operator<<(OStream &os, const std::vector<T> &v) {
    impl::write::all_write(os, v);
    return os;
}

template <class OStream, class T, size_t F, kk2::is_ostream_t<OStream> * = nullptr>
OStream &operator<<(OStream &os, const std::array<T, F> &a) {
    impl::write::all_write(os, a);
    return os;
}

#endif // KK2_TEMPLATE_IO_UTIL_HPP
#ifndef KK2_TEMPLATE_MACROS_HPP
#define KK2_TEMPLATE_MACROS_HPP 1

#define rep1(a) for (long long _ = 0; _ < (long long)(a); ++_)
#define rep2(i, a) for (long long i = 0; i < (long long)(a); ++i)
#define rep3(i, a, b) for (long long i = (a); i < (long long)(b); ++i)
#define repi2(i, a) for (long long i = (a) - 1; i >= 0; --i)
#define repi3(i, a, b) for (long long i = (a) - 1; i >= (long long)(b); --i)
#define overload3(a, b, c, d, ...) d
#define rep(...) overload3(__VA_ARGS__, rep3, rep2, rep1)(__VA_ARGS__)
#define repi(...) overload3(__VA_ARGS__, repi3, repi2, rep1)(__VA_ARGS__)

#define fi first
#define se second
#define all(p) begin(p), end(p)

#endif // KK2_TEMPLATE_MACROS_HPP

struct FastIOSetUp {
    FastIOSetUp() {
        std::ios::sync_with_stdio(false);
        std::cin.tie(nullptr);
    }
} fast_io_set_up;

auto &kin = std::cin;
auto &kout = std::cout;
auto (*kendl)(std::ostream &) = std::endl<char, std::char_traits<char>>;

void Yes(bool b = 1) { kout << (b ? "Yes\n" : "No\n"); }
void No(bool b = 1) { kout << (b ? "No\n" : "Yes\n"); }
void YES(bool b = 1) { kout << (b ? "YES\n" : "NO\n"); }
void NO(bool b = 1) { kout << (b ? "NO\n" : "YES\n"); }
void yes(bool b = 1) { kout << (b ? "yes\n" : "no\n"); }
void no(bool b = 1) { kout << (b ? "no\n" : "yes\n"); }
template <class T, class S> inline bool chmax(T &a, const S &b) { return (a < b ? a = b, 1 : 0); }
template <class T, class S> inline bool chmin(T &a, const S &b) { return (a > b ? a = b, 1 : 0); }

std::istream &operator>>(std::istream &is, u128 &x) {
    std::string s;
    is >> s;
    x = 0;
    for (char c : s) {
        assert('0' <= c && c <= '9');
        x = x * 10 + c - '0';
    }
    return is;
}

std::istream &operator>>(std::istream &is, i128 &x) {
    std::string s;
    is >> s;
    bool neg = s[0] == '-';
    x = 0;
    for (int i = neg; i < (int)s.size(); i++) {
        assert('0' <= s[i] && s[i] <= '9');
        x = x * 10 + s[i] - '0';
    }
    if (neg) x = -x;
    return is;
}

std::ostream &operator<<(std::ostream &os, u128 x) {
    if (x == 0) return os << '0';
    std::string s;
    while (x) {
        s.push_back('0' + x % 10);
        x /= 10;
    }
    std::reverse(s.begin(), s.end());
    return os << s;
}

std::ostream &operator<<(std::ostream &os, i128 x) {
    if (x == 0) return os << '0';
    if (x < 0) {
        os << '-';
        x = -x;
    }
    std::string s;
    while (x) {
        s.push_back('0' + x % 10);
        x /= 10;
    }
    std::reverse(s.begin(), s.end());
    return os << s;
}

#endif // KK2_TEMPLATE_PROCON_HPP
// #include <kk2/template/debug.hpp>
#ifndef KK2_DATA_STRUCTURE_WAVELET_MATRIX_HPP
#define KK2_DATA_STRUCTURE_WAVELET_MATRIX_HPP 1


#ifndef KK2_BIT_BITCOUNT_HPP
#define KK2_BIT_BITCOUNT_HPP 1


#ifndef KK2_TYPE_TRAITS_INTERGRAL_HPP
#define KK2_TYPE_TRAITS_INTERGRAL_HPP 1



namespace kk2 {

#ifndef _MSC_VER

template <typename T> using is_signed_int128 =
    typename std::conditional<std::is_same<T, __int128_t>::value
                                  or std::is_same<T, __int128>::value,
                              std::true_type,
                              std::false_type>::type;

template <typename T> using is_unsigned_int128 =
    typename std::conditional<std::is_same<T, __uint128_t>::value
                                  or std::is_same<T, unsigned __int128>::value,
                              std::true_type,
                              std::false_type>::type;

template <typename T> using is_integral =
    typename std::conditional<std::is_integral<T>::value or is_signed_int128<T>::value
                                  or is_unsigned_int128<T>::value,
                              std::true_type,
                              std::false_type>::type;

template <typename T> using is_signed =
    typename std::conditional<std::is_signed<T>::value or is_signed_int128<T>::value,
                              std::true_type,
                              std::false_type>::type;

template <typename T> using is_unsigned =
    typename std::conditional<std::is_unsigned<T>::value or is_unsigned_int128<T>::value,
                              std::true_type,
                              std::false_type>::type;

template <typename T> using make_unsigned_int128 =
    typename std::conditional<std::is_same<T, __int128_t>::value, __uint128_t, unsigned __int128>;

template <typename T> using to_unsigned =
    typename std::conditional<is_signed_int128<T>::value,
                              make_unsigned_int128<T>,
                              typename std::conditional<std::is_signed<T>::value,
                                                        std::make_unsigned<T>,
                                                        std::common_type<T>>::type>::type;

#else

template <typename T> using is_integral = std::enable_if_t<std::is_integral<T>::value>;
template <typename T> using is_signed = std::enable_if_t<std::is_signed<T>::value>;
template <typename T> using is_unsigned = std::enable_if_t<std::is_unsigned<T>::value>;
template <typename T> using to_unsigned = std::make_unsigned<T>;

#endif // _MSC_VER

template <typename T> using is_integral_t = std::enable_if_t<is_integral<T>::value>;
template <typename T> using is_signed_t = std::enable_if_t<is_signed<T>::value>;
template <typename T> using is_unsigned_t = std::enable_if_t<is_unsigned<T>::value>;

} // namespace kk2

#endif // KK2_TYPE_TRAITS_INTERGRAL_HPP

namespace kk2 {

template <typename T> int ctz(T x) {
    static_assert(is_integral<T>::value);
    assert(x != T(0));

    if constexpr (sizeof(T) <= 4) {
        return __builtin_ctz(x);
    } else if constexpr (sizeof(T) <= 8) {
        return __builtin_ctzll(x);
    } else {
        if (x & 0xffffffffffffffff)
            return __builtin_ctzll((unsigned long long)(x & 0xffffffffffffffff));
        return 64 + __builtin_ctzll((unsigned long long)(x >> 64));
    }
}

template <typename T> int lsb(T x) {
    static_assert(is_integral<T>::value);
    assert(x != T(0));

    return ctz(x);
}

template <typename T> int clz(T x) {
    static_assert(is_integral<T>::value);
    assert(x != T(0));

    if constexpr (sizeof(T) <= 4) {
        return __builtin_clz(x);
    } else if constexpr (sizeof(T) <= 8) {
        return __builtin_clzll(x);
    } else {
        if (x >> 64) return __builtin_clzll((unsigned long long)(x >> 64));
        return 64 + __builtin_clzll((unsigned long long)(x & 0xffffffffffffffff));
    }
}

template <typename T> int msb(T x) {
    static_assert(is_integral<T>::value);
    assert(x != T(0));

    return sizeof(T) * 8 - 1 - clz(x);
}

template <typename T> int popcount(T x) {
    static_assert(is_integral<T>::value);

    if constexpr (sizeof(T) <= 4) {
        return __builtin_popcount(x);
    } else if constexpr (sizeof(T) <= 8) {
        return __builtin_popcountll(x);
    } else {
        return __builtin_popcountll((unsigned long long)(x >> 64))
               + __builtin_popcountll((unsigned long long)(x & 0xffffffffffffffff));
    }
}

}; // namespace kk2

#endif // KK2_BIT_BITCOUNT_HPP
#ifndef KK2_DATA_STRUCTURE_BIT_VECTOR_HPP
#define KK2_DATA_STRUCTURE_BIT_VECTOR_HPP 1



namespace kk2 {

struct BitVector {
    using u32 = unsigned int;
    using Uint = unsigned long long;
    static constexpr int B = 64;
    int n, zeros;
    std::vector<u32> count;
    std::vector<Uint> bits;
    BitVector() = default;

    BitVector(int n_) : n(n_), count(n_ / B + 1), bits(n_ / B + 1) {}

    inline void set(int i) { bits[i / B] |= Uint(1) << (i % B); }

    void build() {
        for (u32 i = 1; i < count.size(); ++i) count[i] = count[i - 1] + popcount(bits[i - 1]);
        zeros = n - rank1(n);
    }

    inline int get(int i) const { return (bits[i / B] >> (i % B)) & 1; }

    inline int rank0(int i) const { return i - rank1(i); }

    inline int rank1(int i) const {
        return count[i / B] + popcount(bits[i / B] & ((Uint(1) << (i % B)) - 1));
    }

    int select0(int i) const {
        if (i >= zeros) return -1;
        int lb = 0, ub = n;
        while (ub - lb > 1) {
            int mid = (lb + ub) / 2;
            if (rank0(mid) > i) ub = mid;
            else lb = mid;
        }
        return lb;
    }

    int select1(int i) const {
        if (i >= n - zeros) return -1;
        int lb = 0, ub = n;
        while (ub - lb > 1) {
            int mid = (lb + ub) / 2;
            if (rank1(mid) > i) ub = mid;
            else lb = mid;
        }
        return lb;
    }
};

} // namespace kk2

#endif // KK2_DATA_STRUCTURE_BIT_VECTOR_HPP

namespace kk2 {

template <typename T> struct WaveletMatrix {
    int n, lg;
    std::vector<T> a;
    std::vector<BitVector> mat;
    bool built = false;

    WaveletMatrix() = default;

    WaveletMatrix(int n_) : n(n_) {}

    WaveletMatrix(const std::vector<T> &a_) : n(a_.size()), a(a_) { build(); }

    void build() {
        built = true;
        lg = 0;
        T mx = *std::max_element(a.begin(), a.end());
        if (mx <= 0) mx = 1;
        lg = msb(mx) + 1;
        mat.resize(lg, BitVector(n));
        std::vector<T> now(a), nxt(n);
        for (int i = lg - 1; i >= 0; --i) {
            BitVector &bv = mat[i];
            for (int j = 0; j < n; ++j) {
                if ((now[j] >> i) & 1) bv.set(j);
            }
            bv.build();
            int one = bv.zeros, zero = 0;
            for (int j = 0; j < n; ++j) {
                if ((now[j] >> i) & 1) {
                    nxt[one++] = now[j];
                } else {
                    nxt[zero++] = now[j];
                }
            }
            std::swap(now, nxt);
        }
    }

    void set(int i, T x) {
        assert(0 <= i && i < n);
        assert(x >= 0);
        assert(!built);
        a[i] = x;
    }

    T access(int k) const {
        assert(0 <= k && k < n);
        return a[k];
    }

    int rank(T b, int k) {
        assert(0 <= k && k <= n);
        int l = 0, r = k;
        for (int i = lg - 1; i >= 0; --i) {
            r = (b >> i & 1) ? mat[i].rank1(r) + mat[i].zeros : mat[i].rank0(r);
            l = (b >> i & 1) ? mat[i].rank1(l) + mat[i].zeros : mat[i].rank0(l);
        }
        return r - l;
    }

    int select(T b, int k) {
        assert(0 <= k && k < n);
        int l = 0;
        for (int i = lg - 1; i >= 0; --i)
            l = (b >> i & 1) ? mat[i].rank1(l) + mat[i].zeros : mat[i].rank0(l);
        k += l;
        for (int i = 0; i < lg; ++i) {
            k = (b >> i & 1) ? mat[i].select1(k - mat[i].zeros) : mat[i].select0(k);
            if (k == -1) return -1;
        }
        return k;
    }

    T kth_smallest(int l, int r, int k) const {
        assert(0 <= l && l <= r && r <= n);
        assert(r - l > k);
        T res = 0;
        for (int i = lg - 1; i >= 0; --i) {
            int ll = mat[i].rank0(l), rr = mat[i].rank0(r);
            if (k < rr - ll) {
                l = ll, r = rr;
            } else {
                k -= rr - ll;
                res |= T(1) << i;
                l += mat[i].zeros - ll;
                r += mat[i].zeros - rr;
            }
        }
        return res;
    }

    T kth_largest(int l, int r, int k) const {
        assert(0 <= l && l <= r && r <= n);
        assert(r - l > k);
        return kth_smallest(l, r, r - l - k - 1);
    }

    int range_freq(int l, int r, T upper) const {
        assert(0 <= l && l <= r && r <= n);
        assert(0 <= upper);
        if (upper >> lg) return r - l;
        int res = 0;
        for (int i = lg - 1; i >= 0; --i) {
            if (upper >> i & 1) res += mat[i].rank0(r) - mat[i].rank0(l);
            l = (upper >> i & 1) ? mat[i].rank1(l) + mat[i].zeros : mat[i].rank0(l);
            r = (upper >> i & 1) ? mat[i].rank1(r) + mat[i].zeros : mat[i].rank0(r);
            if (l == r) break;
        }
        return res;
    }

    int range_freq(int l, int r, T lower, T upper) {
        assert(0 <= l && l <= r && r <= n);
        assert(0 <= lower && lower <= upper);
        return range_freq(l, r, upper) - range_freq(l, r, lower);
    }

    T max_not_greater(int l, int r, T b) {
        assert(0 <= l && l <= r && r <= n);
        int count = range_freq(l, r, b + 1);
        return count == 0 ? -1 : kth_smallest(l, r, count - 1);
    }

    T min_not_less(int l, int r, T b) {
        assert(0 <= l && l <= r && r <= n);
        int count = range_freq(l, r, b);
        return count == r - l ? -1 : kth_smallest(l, r, count);
    }
};

} // namespace kk2


#endif // KK2_DATA_STRUCTURE_WAVELET_MATRIX_HPP
#ifndef KK2_MATH_LPF_TABLE_HPP
#define KK2_MATH_LPF_TABLE_HPP 1


namespace kk2 {

struct LPFTable {
  private:
    static inline std::vector<int> _primes{2}, _lpf{};

  public:
    LPFTable() = delete;

    static void set_upper(int m, int reserve_size = 26355867) {
        if ((int)_lpf.size() == 0) _primes.reserve(reserve_size);
        if ((int)_lpf.size() > m) return;
        m = std::max<int>(2 * _lpf.size(), m);
        _lpf.resize(m + 1);
        iota(_lpf.begin(), _lpf.end(), 0);
        for (int i = 2; i <= m; i++) {
            if (_lpf[i] == i and _primes.back() < i) _primes.emplace_back(i);
            for (const long long p : _primes) {
                if (p * i > m) break;
                if (_lpf[i] < p) break;
                _lpf[p * i] = p;
            }
        }
    }

    static const std::vector<int> &primes() { return _primes; }

    template <typename It> struct PrimeIt {
        It bg, ed;

        PrimeIt(It bg_, It ed_) : bg(bg_), ed(ed_) {}

        It begin() const { return bg; }

        It end() const { return ed; }

        int size() const { return ed - bg; }

        int operator[](int i) const { return bg[i]; }

        std::vector<int> to_vec() const { return std::vector<int>(bg, ed); }
    };

    static auto primes(int n) {
        if (n >= (int)_lpf.size()) set_upper(n);
        return PrimeIt(_primes.begin(), std::upper_bound(_primes.begin(), _primes.end(), n));
    }

    static int lpf(int n) {
        assert(n > 1);
        if (n >= (int)_lpf.size()) set_upper(n);
        return _lpf[n];
    }

    static bool isprime(int n) {
        assert(n > 0);
        if (n >= (int)_lpf.size()) set_upper(n);
        return n != 1 and _lpf[n] == n;
    }
};

} // namespace kk2


#endif // KK2_MATH_LPF_TABLE_HPP
using namespace std;

void solve() {
    /*
    右が無限に長いとして,行動していったものを見ればよい
    食べられる iff 自分以外の最大の約数がL未満
    WMなど
    */

    using lpft = kk2::LPFTable;
    lpft::set_upper(1e6);
    vc<int> a(1e6 + 1);
    rep (i, 2, 1e6 + 1) a[i] = i / lpft::lpf(i);
    kk2::WaveletMatrix<int> wm(a);

    int q;
    kin >> q;
    rep (q) {
        int l, r;
        kin >> l >> r;
        if (l == 1) {
            kout << 1 << "\n";
            continue;
        }
        kout << wm.range_freq(l, r + 1, l) << "\n";
    }

}

int main() {
    int t = 1;
    // kin >> t;
    rep (t) solve();

    return 0;
}
// Author: kk2
// converted by https://github.com/kk2a/cpp-bundle
// 2025-04-11 23:17:28
0