// [TEMPLATE_BEGIN]
#include <bits/stdc++.h>

#include <iostream>
#include <tuple>
#include <type_traits>
#include <vector>

// ==================== 単一値・基本入力 ====================

/**
 * @brief 標準入出力の高速化を行う。main関数の最初で呼ぶことを推奨。
 */
inline void fast_io() {
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(nullptr);
}

/**
 * @brief 任意の数の変数を標準入力から読み込む
 * @tparam Ts 引数の型パック
 * @param args 読み込み先の変数
 */
template <typename... Ts>
inline void scan(Ts&... args) {
    (std::cin >> ... >> args);
}

/**
 * @brief 単一の値を標準入力から読み込む
 * @tparam T 読み込む値の型 (デフォルト: int)
 * @return 読み込んだ値
 */
template <typename T = int>
inline T read() {
    T x;
    std::cin >> x;
    return x;
}

// ==================== ベクター入力 ====================

/**
 * @brief 1次元ベクターを標準入力から読み込む（算術型用、offset 付き）
 * @tparam T 要素の型 (デフォルト: int)
 * @param n 要素数
 * @param offset 読み込み時に引く値 (デフォルト: 0)
 * @return 読み込んだベクター
 */
template <typename T = int>
    requires std::is_arithmetic_v<T>
inline std::vector<T> read_vec(int n, T offset = 0) {
    std::vector<T> v(n);
    for (auto& x : v) {
        std::cin >> x;
        x -= offset;
    }
    return v;
}

/**
 * @brief 1次元ベクターを標準入力から読み込む（非算術型用）
 * @tparam T 要素の型
 * @param n 要素数
 * @return 読み込んだベクター
 */
template <typename T>
    requires(!std::is_arithmetic_v<T>)
inline std::vector<T> read_vec(int n) {
    std::vector<T> v(n);
    for (auto& x : v) {
        std::cin >> x;
    }
    return v;
}

/**
 * @brief 2次元ベクターを標準入力から読み込む（算術型用、offset 付き）
 * @tparam T 要素の型 (デフォルト: int)
 * @param h 行数
 * @param w 列数
 * @param offset 読み込み時に引く値 (デフォルト: 0)
 * @return 読み込んだ h×w の2次元ベクター
 */
template <typename T = int>
    requires std::is_arithmetic_v<T>
inline std::vector<std::vector<T>> read_vec2(int h, int w, T offset = 0) {
    std::vector<std::vector<T>> v(h, std::vector<T>(w));
    for (auto& row : v) {
        for (auto& x : row) {
            std::cin >> x;
            x -= offset;
        }
    }
    return v;
}

/**
 * @brief 2次元ベクターを標準入力から読み込む（非算術型用）
 * @tparam T 要素の型
 * @param h 行数
 * @param w 列数
 * @return 読み込んだ h×w の2次元ベクター
 */
template <typename T>
    requires(!std::is_arithmetic_v<T>)
inline std::vector<std::vector<T>> read_vec2(int h, int w) {
    std::vector<std::vector<T>> v(h, std::vector<T>(w));
    for (auto& row : v) {
        for (auto& x : row) {
            std::cin >> x;
        }
    }
    return v;
}

/**
 * @brief 各行の最初に要素数が与えられる可変長2次元ベクターを標準入力から読み込む（算術型用、offset 付き）
 * @tparam T 要素の型 (デフォルト: int)
 * @param h 行数
 * @param offset 読み込み時に引く値 (デフォルト: 0)
 * @return 読み込んだ可変長の2次元ベクター
 */
template <typename T = int>
    requires std::is_arithmetic_v<T>
inline std::vector<std::vector<T>> read_vec2_var(int h, T offset = 0) {
    std::vector<std::vector<T>> v(h);
    for (auto& row : v) {
        int m;
        std::cin >> m;
        row = read_vec<T>(m, offset);
    }
    return v;
}

/**
 * @brief 各行の最初に要素数が与えられる可変長2次元ベクターを標準入力から読み込む（非算術型用）
 * @tparam T 要素の型
 * @param h 行数
 * @return 読み込んだ可変長の2次元ベクター
 */
template <typename T>
    requires(!std::is_arithmetic_v<T>)
inline std::vector<std::vector<T>> read_vec2_var(int h) {
    std::vector<std::vector<T>> v(h);
    for (auto& row : v) {
        int m;
        std::cin >> m;
        row = read_vec<T>(m);
    }
    return v;
}

/**
 * @brief 1次元のペアのベクターを標準入力から読み込む
 * @tparam T1 ペアの1つ目の要素の型 (デフォルト: int)
 * @tparam T2 ペアの2つ目の要素の型 (デフォルト: int)
 * @param n 要素数
 * @param offset1 1つ目の要素から引く値 (デフォルト: 0)
 * @param offset2 2つ目の要素から引く値 (デフォルト: 0)
 * @return 読み込んだペアのベクター
 */
template <typename T1 = int, typename T2 = int>
inline std::vector<std::pair<T1, T2>> read_vec_pair(int n, T1 offset1 = 0, T2 offset2 = 0) {
    std::vector<std::pair<T1, T2>> v(n);
    for (auto& [x, y] : v) {
        std::cin >> x >> y;
        x -= offset1;
        y -= offset2;
    }
    return v;
}

// ==================== 行列・三角形入力 ====================

/**
 * @brief 上三角行列形式の入力を読み込み、2次元ベクターとして返す（算術型用、offset 付き）
 * @tparam T 要素の型 (デフォルト: int)
 * @param n 行列のサイズ (n x n)
 * @param symmetric 対称行列にするかどうか (デフォルト: true)
 * @param offset 読み込み時に値から引く量 (デフォルト: 0)
 * @return 読み込んだ 2次元ベクター
 */
template <typename T = int>
    requires std::is_arithmetic_v<T>
inline std::vector<std::vector<T>> read_upper_tri(int n, bool symmetric = true, T offset = 0) {
    std::vector<std::vector<T>> v(n, std::vector<T>(n));
    for (int i = 0; i < n - 1; ++i) {
        for (int j = i + 1; j < n; ++j) {
            std::cin >> v[i][j];
            v[i][j] -= offset;
            if (symmetric) v[j][i] = v[i][j];
        }
    }
    return v;
}

/**
 * @brief 上三角行列形式の入力を読み込み、2次元ベクターとして返す（非算術型用）
 * @tparam T 要素の型
 * @param n 行列のサイズ (n x n)
 * @param symmetric 対称行列にするかどうか (デフォルト: true)
 * @return 読み込んだ 2次元ベクター
 */
template <typename T>
    requires(!std::is_arithmetic_v<T>)
inline std::vector<std::vector<T>> read_upper_tri(int n, bool symmetric = true) {
    std::vector<std::vector<T>> v(n, std::vector<T>(n));
    for (int i = 0; i < n - 1; ++i) {
        for (int j = i + 1; j < n; ++j) {
            std::cin >> v[i][j];
            if (symmetric) v[j][i] = v[i][j];
        }
    }
    return v;
}

/**
 * @brief 下三角行列形式の入力を読み込み、2次元ベクターとして返す（算術型用、offset 付き）
 * @tparam T 要素の型 (デフォルト: int)
 * @param n 行列のサイズ (n x n)
 * @param symmetric 対称行列にするかどうか (デフォルト: true)
 * @param offset 読み込み時に値から引く量 (デフォルト: 0)
 * @return 読み込んだ 2次元ベクター
 */
template <typename T = int>
    requires std::is_arithmetic_v<T>
inline std::vector<std::vector<T>> read_lower_tri(int n, bool symmetric = true, T offset = 0) {
    std::vector<std::vector<T>> v(n, std::vector<T>(n));
    for (int i = 1; i < n; ++i) {
        for (int j = 0; j < i; ++j) {
            std::cin >> v[i][j];
            v[i][j] -= offset;
            if (symmetric) v[j][i] = v[i][j];
        }
    }
    return v;
}

/**
 * @brief 下三角行列形式の入力を読み込み、2次元ベクターとして返す（非算術型用）
 * @tparam T 要素の型
 * @param n 行列のサイズ (n x n)
 * @param symmetric 对称行列にするかどうか (デフォルト: true)
 * @return 読み込んだ 2次元ベクター
 */
template <typename T>
    requires(!std::is_arithmetic_v<T>)
inline std::vector<std::vector<T>> read_lower_tri(int n, bool symmetric = true) {
    std::vector<std::vector<T>> v(n, std::vector<T>(n));
    for (int i = 1; i < n; ++i) {
        for (int j = 0; j < i; ++j) {
            std::cin >> v[i][j];
            if (symmetric) v[j][i] = v[i][j];
        }
    }
    return v;
}

// ==================== タプル入力 ====================

namespace detail {

/**
 * @brief タプルの各要素を順番に読み込む（内部実装）
 * @tparam Tuple タプル型
 * @tparam Is インデックスのパック
 * @param t 読み込み先のタプル
 */
template <typename Tuple, std::size_t... Is>
inline void read_tuple_impl(Tuple& t, std::index_sequence<Is...>) {
    (std::cin >> ... >> std::get<Is>(t));
}

}  // namespace detail

/**
 * @brief 複数の型の値をまとめてタプルとして読み込む
 * @tparam Ts 読み込む型のパック
 * @return 読み込んだ値を格納した std::tuple<Ts...>
 *
 * 使い方:
 *   auto [a, b, c] = read_tuple<int, long long, std::string>();
 */
template <typename... Ts>
inline std::tuple<Ts...> read_tuple() {
    std::tuple<Ts...> t;
    detail::read_tuple_impl(t, std::index_sequence_for<Ts...>{});
    return t;
}

/**
 * @brief n 行分のタプルをベクターとして読み込む
 * @tparam Ts 各行の型のパック
 * @param n 行数
 * @return 読み込んだ std::tuple<Ts...> の std::vector
 *
 * 使い方:
 *   auto v = read_vec_tuple<int, int, long long>(n);
 *   auto [a, b, c] = v[i];
 */
template <typename... Ts>
inline std::vector<std::tuple<Ts...>> read_vec_tuple(int n) {
    std::vector<std::tuple<Ts...>> v(n);
    for (auto& t : v)
        detail::read_tuple_impl(t, std::index_sequence_for<Ts...>{});
    return v;
}

// ==================== グラフ入力 ====================

/**
 * @brief 無向グラフを辺リストから隣接リスト形式で読み込む
 * @param n 頂点数
 * @param m 辺数
 * @param base 入力の頂点番号のベース (0-indexed なら 0、1-indexed なら 1)
 * @return 0-indexed の隣接リスト (vector<vector<int>>)
 *
 * 使い方:
 *   auto g = read_graph(n, m, 1); // 1-indexed 入力
 */
inline std::vector<std::vector<int>> read_graph(int n, int m, int base = 1) {
    std::vector<std::vector<int>> g(n);
    for (int i = 0; i < m; i++) {
        int u, v;
        std::cin >> u >> v;
        u -= base;
        v -= base;
        g[u].push_back(v);
        g[v].push_back(u);
    }
    return g;
}

/**
 * @brief 有向グラフを辺リストから隣接リスト形式で読み込む
 * @param n 頂点数
 * @param m 辺数
 * @param base 入力の頂点番号のベース (0-indexed なら 0、1-indexed なら 1)
 * @return 0-indexed の隣接リスト (vector<vector<int>>)
 *
 * 使い方:
 *   auto g = read_digraph(n, m, 1); // 1-indexed 入力、u -> v の有向辺
 */
inline std::vector<std::vector<int>> read_digraph(int n, int m, int base = 1) {
    std::vector<std::vector<int>> g(n);
    for (int i = 0; i < m; i++) {
        int u, v;
        std::cin >> u >> v;
        u -= base;
        v -= base;
        g[u].push_back(v);
    }
    return g;
}

/**
 * @brief 木を辺リストから隣接リスト形式で読み込む (n-1 辺)
 * @param n 頂点数
 * @param base 入力の頂点番号のベース (0-indexed なら 0、1-indexed なら 1)
 * @return 0-indexed の隣接リスト (vector<vector<int>>)
 *
 * 使い方:
 *   auto g = read_tree(n, 1); // 1-indexed 入力
 */
inline std::vector<std::vector<int>> read_tree(int n, int base = 1) {
    return read_graph(n, n - 1, base);
}

/**
 * @brief 重み付き木を辺リストから隣接リスト形式で読み込む (n-1 辺)
 * @tparam W 辺の重みの型
 * @param n 頂点数
 * @param base 入力の頂点番号のベース (0-indexed なら 0、1-indexed なら 1)
 * @return 0-indexed の隣接リスト。各エントリは {隣接頂点, 重み} のペア
 *
 * 使い方:
 *   auto g = read_weighted_tree<long long>(n, 1);
 */
template <typename W>
inline std::vector<std::vector<std::pair<int, W>>> read_weighted_tree(int n, int base = 1) {
    return read_weighted_graph<W>(n, n - 1, base);
}

/**
 * @brief 重み付き無向グラフを辺リストから隣接リスト形式で読み込む
 * @tparam W 辺の重みの型
 * @param n 頂点数
 * @param m 辺数
 * @param base 入力の頂点番号のベース (0-indexed なら 0、1-indexed なら 1)
 * @return 0-indexed の隣接リスト。各エントリは {隣接頂点, 重み} のペア
 *
 * 使い方:
 *   auto g = read_weighted_graph<long long>(n, m, 1);
 *   for (auto [v, w] : g[u]) { ... }
 */
template <typename W>
inline std::vector<std::vector<std::pair<int, W>>> read_weighted_graph(int n, int m, int base = 1) {
    std::vector<std::vector<std::pair<int, W>>> g(n);
    for (int i = 0; i < m; i++) {
        int u, v;
        W w;
        std::cin >> u >> v >> w;
        u -= base;
        v -= base;
        g[u].emplace_back(v, w);
        g[v].emplace_back(u, w);
    }
    return g;
}

/**
 * @brief 重み付き有向グラフを辺リストから隣接リスト形式で読み込む
 * @tparam W 辺の重みの型
 * @param n 頂点数
 * @param m 辺数
 * @param base 入力の頂点番号のベース (0-indexed なら 0、1-indexed なら 1)
 * @return 0-indexed の隣接リスト。各エントリは {隣接頂点, 重み} のペア
 *
 * 使い方:
 *   auto g = read_weighted_digraph<long long>(n, m, 1);
 *   for (auto [v, w] : g[u]) { ... }
 */
template <typename W>
inline std::vector<std::vector<std::pair<int, W>>> read_weighted_digraph(int n, int m, int base = 1) {
    std::vector<std::vector<std::pair<int, W>>> g(n);
    for (int i = 0; i < m; i++) {
        int u, v;
        W w;
        std::cin >> u >> v >> w;
        u -= base;
        v -= base;
        g[u].emplace_back(v, w);
    }
    return g;
}

// ==================== 辺リスト入力 ====================

/**
 * @brief 無向/有向グラフの辺リストを読み込む
 * @param m 辺数
 * @param base 入力の頂点番号のベース (0-indexed なら 0、1-indexed なら 1)
 * @return 0-indexed の辺リスト (std::vector<std::pair<int, int>>)
 */
inline std::vector<std::pair<int, int>> read_edges(int m, int base = 1) {
    std::vector<std::pair<int, int>> edges(m);
    for (int i = 0; i < m; ++i) {
        int u, v;
        std::cin >> u >> v;
        edges[i] = {u - base, v - base};
    }
    return edges;
}

/**
 * @brief 重み付き無向/有向グラフの辺リストを読み込む
 * @tparam W 辺の重みの型
 * @param m 辺数
 * @param base 入力の頂点番号のベース (0-indexed なら 0、1-indexed なら 1)
 * @return 0-indexed の重み付き辺リスト (std::vector<std::tuple<int, int, W>>)
 */
template <typename W>
inline std::vector<std::tuple<int, int, W>> read_weighted_edges(int m, int base = 1) {
    std::vector<std::tuple<int, int, W>> edges(m);
    for (int i = 0; i < m; ++i) {
        int u, v;
        W w;
        std::cin >> u >> v >> w;
        edges[i] = {u - base, v - base, w};
    }
    return edges;
}
#include <algorithm>
#include <concepts>
#include <numeric>
#include <print>
#include <vector>
#include <tuple>

/**
 * @brief aをaとbの最小値で更新
 * @param a 更新対象
 * @param b 比較値
 * @return 更新されたらtrue
 */
template <typename T, typename U>
inline bool chmin(T& a, const U& b) {
    if (a > b) {
        a = b;
        return true;
    }
    return false;
}

/**
 * @brief aをaとbの最大値で更新
 * @param a 更新対象
 * @param b 比較値
 * @return 更新されたらtrue
 */
template <typename T, typename U>
inline bool chmax(T& a, const U& b) {
    if (a < b) {
        a = b;
        return true;
    }
    return false;
}

/**
 * @brief 整数除算の切り上げ (b>0)
 * @param a 分子
 * @param b 分母
 * @return 切り上げ値
 */
template <std::integral T>
inline T div_ceil(T a, T b) {
    if (a >= 0) return (a + b - 1) / b;
    return a / b;
}

/**
 * @brief 整数除算の切り捨て (b>0)
 * @param a 分子
 * @param b 分母
 * @return 切り捨て値
 */
template <std::integral T>
inline T div_floor(T a, T b) {
    if (a >= 0) return a / b;
    return (a - b + 1) / b;
}

/**
 * @brief 連続整数のvector生成
 * @param n 要素数
 * @param start 開始値(デフォルト0)
 * @return 生成されたvector
 */
template <typename T = int>
inline std::vector<T> iota_vec(int n, T start = 0) {
    std::vector<T> v(n);
    std::iota(v.begin(), v.end(), start);
    return v;
}

namespace internal {
/**
 * @brief 多次元のstd::vectorをデフォルト値で生成するヘルパー
 */
template <typename T, typename... Args>
inline auto make_vec_default(int n, Args... args) {
    if constexpr (sizeof...(args) == 0) {
        return std::vector<T>(n);
    } else {
        return std::vector(n, make_vec_default<T>(args...));
    }
}
}  // namespace internal

/**
 * @brief 多次元のstd::vectorを初期値付きで生成する
 * @param n サイズ
 * @param init 初期値
 * @return 1次元のstd::vector
 */
template <typename T>
inline std::vector<T> make_vec(int n, const T& init) {
    return std::vector<T>(n, init);
}

/**
 * @brief 多次元のstd::vectorを初期値付きで生成する（再帰・推論）
 * @param n 最初の次元のサイズ
 * @param args 残りの次元のサイズ、および最終的な初期値
 * @return 多次元のstd::vector
 */
template <typename... Args>
inline auto make_vec(int n, Args... args) {
    return std::vector(n, make_vec(args...));
}

/**
 * @brief 多次元のstd::vectorをデフォルト値で生成する
 * @tparam T 要素の型
 * @param args 次元のサイズ列
 * @return 多次元のstd::vector
 */
template <typename T, typename... Args>
inline auto make_vec(Args... args) {
    return internal::make_vec_default<T>(args...);
}

/**
 * @brief 同じサイズの複数の多次元のstd::vectorを生成する
 * @tparam Ts 各vectorの要素型
 * @param args 次元のサイズ列
 * @return 生成された各テーブルを格納したstd::tuple
 */
template <typename... Ts, typename... Args>
inline auto make_vecs(Args... args) {
    return std::make_tuple(internal::make_vec_default<Ts>(args...)...);
}


/**
 * @brief vectorを2回反復連結
 * @param v 元のvector
 * @return 2倍長のvector
 */
template <typename T>
inline std::vector<T> doubled(const std::vector<T>& v) {
    std::vector<T> res;
    res.reserve(v.size() * 2);
    res.insert(res.end(), v.begin(), v.end());
    res.insert(res.end(), v.begin(), v.end());
    return res;
}

/**
 * @brief 区間[l1,r1)と[l2,r2)の共通長
 * @param l1 区間1左端
 * @param r1 区間1右端
 * @param l2 区間2左端
 * @param r2 区間2右端
 * @return 共通部分の長さ(ない場合は0)
 */
template <typename T>
inline T overlap_length(T l1, T r1, T l2, T r2) {
    return std::max(static_cast<T>(0), std::min(r1, r2) - std::max(l1, l2));
}

/**
 * @brief "Yes"/"No"を出力
 * @param b trueでYes, falseでNo
 */
inline void Yes(bool b = true) {
    std::println("{}", (b ? "Yes" : "No"));
}

/**
 * @brief "No"を出力
 */
inline void No() {
    std::println("No");
}

#ifdef LOCAL
#include <library/my_library/utility/debug.hpp>
#else
#define debug(...)
#endif

using namespace std;
namespace rv = std::views;  // NOLINT

using lint = long long;
#define ALL(a) (a).begin(), (a).end()
// [TEMPLATE_END]

#include <algorithm>
#include <chrono>
#include <cstdint>
#include <numeric>
#include <random>
#include <vector>

namespace prime {

/**
 * @brief 素数・約数ライブラリ
 *
 * ◆ 素数判定
 *   is_prime_mr(n)           Miller-Rabin (64bit対応, 決定的)
 *
 * ◆ 素因数分解
 *   factorize(n)             試し割り法 O(√N)
 *   factorize_fast(n)        Pollard's Rho O(N^{1/4})
 *
 * ◆ 約数列挙
 *   divisors(n)              O(√N)
 *
 * ◆ 篩 (前処理ベース)
 *   Eratosthenes sieve(n)    エラトステネスの篩
 *     sieve.is_prime(x) / sieve.primes() / sieve.factorize(x) / sieve.divisors(x)
 *   LinearSieve sieve(n)     線形篩 (φ, μ 付き)
 *     sieve.is_prime(x) / sieve.primes / sieve.phi / sieve.mobius / sieve.factorize(x)
 *
 * ◆ 区間篩
 *   segment_sieve(L, R)      [L, R] の素数リスト
 *   segment_sieve_bool(L, R) [L, R] の素数判定テーブル
 *   count_primes_range(L, R) [L, R] の素数の個数
 *
 * ◆ ユーティリティ
 *   prime_count_table(n)                 i 以下の素数の個数テーブル
 *   distinct_prime_factor_count_table(n) 互いに異なる素因数の個数テーブル (ω(n))
 *   total_prime_factor_count_table(n)    素因数の総数テーブル (Ω(n))
 *   euler_phi(n)                         オイラーのφ関数 (単発)
 */

// ============================================================
// 内部ユーティリティ
// ============================================================

namespace internal {

/**
 * @brief オーバーフロー安全な mod 乗算
 * @param a 乗算する値
 * @param b 乗算する値
 * @param mod 法
 * @return a * b mod mod
 */
inline long long mod_mul(long long a, long long b, long long mod) { return (__int128)a * b % mod; }

/**
 * @brief mod べき乗
 * @param base 底
 * @param exp 指数
 * @param mod 法
 * @return base^exp mod mod
 */
inline long long mod_pow(long long base, long long exp, long long mod) {
    long long result = 1;
    base %= mod;
    while (exp > 0) {
        if (exp & 1) result = mod_mul(result, base, mod);
        base = mod_mul(base, base, mod);
        exp >>= 1;
    }
    return result;
}

}  // namespace internal

// ============================================================
// 素数判定
// ============================================================

/**
 * @brief Miller-Rabin 素数判定 (64bit対応)
 *
 * 決定的判定。2^63 未満の全ての整数に対して正しく判定する。
 *
 * @param n 判定する数
 * @return 素数なら true
 */
inline bool is_prime_mr(long long n) {
    if (n < 2) return false;
    if (n == 2 || n == 3) return true;
    if (n % 2 == 0) return false;

    long long d = n - 1;
    int r = 0;
    while (d % 2 == 0) {
        d /= 2;
        r++;
    }

    auto mod_pow = [](long long base, long long exp, long long mod) {
        long long result = 1;
        base %= mod;
        while (exp > 0) {
            if (exp & 1) result = (__int128)result * base % mod;
            base = (__int128)base * base % mod;
            exp >>= 1;
        }
        return result;
    };

    // 決定的テスト用の証拠
    static const std::vector<long long> witnesses = {2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37};

    for (long long a : witnesses) {
        if (a >= n) continue;
        long long x = mod_pow(a, d, n);
        if (x == 1 || x == n - 1) continue;

        bool composite = true;
        for (int i = 0; i < r - 1; i++) {
            x = (__int128)x * x % n;
            if (x == n - 1) {
                composite = false;
                break;
            }
        }
        if (composite) return false;
    }
    return true;
}

// ============================================================
// 素因数分解
// ============================================================

/**
 * @brief 素因数分解 (試し割り法)
 *
 * 計算量: O(√N)
 *
 * @param n 素因数分解する数
 * @return (素因数, 指数) のペアの配列
 */
inline std::vector<std::pair<long long, int>> factorize(long long n) {
    std::vector<std::pair<long long, int>> result;
    for (long long p = 2; p * p <= n; p++) {
        if (n % p == 0) {
            int cnt = 0;
            while (n % p == 0) {
                n /= p;
                cnt++;
            }
            result.emplace_back(p, cnt);
        }
    }
    if (n > 1) result.emplace_back(n, 1);
    return result;
}

namespace internal {

/**
 * @brief Pollard's rho アルゴリズム (Brent 変法)
 *
 * n の非自明な因数を1つ返す。
 * n が偶数なら 2 を返し、素数なら n 自身を返す。
 *
 * @param n 因数を求める合成数 (n >= 2)
 * @return n の非自明な因数
 */
inline long long pollard_rho(long long n) {
    if (n % 2 == 0) return 2;
    if (is_prime_mr(n)) return n;

    static std::mt19937_64 rng(std::chrono::steady_clock::now().time_since_epoch().count());

    while (true) {
        long long c = rng() % (n - 1) + 1;
        auto f = [&](long long x) { return (mod_mul(x, x, n) + c) % n; };

        long long x = rng() % (n - 2) + 2;
        long long y = x;
        long long g = 1;

        // Brent の周期検出 + GCD バッチング
        while (g == 1) {
            long long ys = y;
            long long q = 1;
            constexpr int batch = 128;

            for (int r = 1; g == 1; r <<= 1) {
                x = y;
                for (int i = 0; i < r; i++) y = f(y);
                for (int k = 0; g == 1 && k < r; k += batch) {
                    ys = y;
                    int bound = std::min(batch, r - k);
                    for (int i = 0; i < bound; i++) {
                        y = f(y);
                        q = mod_mul(q, std::abs(x - y), n);
                    }
                    g = std::gcd(q, n);
                }
            }

            // バッチングで g == n になった場合、1ステップずつ再試行
            if (g == n) {
                g = 1;
                while (g == 1) {
                    ys = f(ys);
                    g = std::gcd(std::abs(x - ys), n);
                }
            }
        }
        if (g != n) return g;
    }
}

/**
 * @brief 再帰的に素因数を収集する内部関数
 * @param n 素因数分解する数
 * @param result 素因数を追加するベクタ
 */
inline void collect_factors(long long n, std::vector<long long>& result) {
    if (n <= 1) return;
    if (is_prime_mr(n)) {
        result.push_back(n);
        return;
    }
    long long d = pollard_rho(n);
    collect_factors(d, result);
    collect_factors(n / d, result);
}

}  // namespace internal

/**
 * @brief 高速素因数分解 (Miller-Rabin + Pollard's Rho)
 *
 * 期待計算量 O(N^{1/4} polylog N)
 * 試し割り法 (O(√N)) より大幅に高速。
 * N ≤ 9×10^18 程度まで対応。
 *
 * @param n 素因数分解する数
 * @return (素因数, 指数) のペアの配列 (素因数の昇順)
 *
 * @example
 * auto factors = prime::factorize_fast(1000000007LL * 998244353LL);
 * // => {{998244353, 1}, {1000000007, 1}}
 */
inline std::vector<std::pair<long long, int>> factorize_fast(long long n) {
    std::vector<long long> primes;
    internal::collect_factors(n, primes);
    std::sort(primes.begin(), primes.end());

    std::vector<std::pair<long long, int>> result;
    for (long long p : primes) {
        if (!result.empty() && result.back().first == p) {
            result.back().second++;
        } else {
            result.emplace_back(p, 1);
        }
    }
    return result;
}

// ============================================================
// 約数列挙
// ============================================================

/**
 * @brief 約数列挙
 *
 * 計算量: O(√N)
 *
 * @param n 約数を列挙する数
 * @return 約数の配列 (昇順)
 */
inline std::vector<long long> divisors(long long n) {
    std::vector<long long> small, large;
    for (long long i = 1; i * i <= n; i++) {
        if (n % i == 0) {
            small.push_back(i);
            if (i != n / i) large.push_back(n / i);
        }
    }
    for (int i = (int)large.size() - 1; i >= 0; i--) small.push_back(large[i]);
    return small;
}

// ============================================================
// 篩 (前処理ベース)
// ============================================================

/**
 * @brief エラトステネスの篩
 *
 * 計算量: O(N log log N) 前処理
 * 素数列挙・素数判定・高速素因数分解・約数列挙を提供する。
 *
 * @example
 * Eratosthenes sieve(1000000);
 * sieve.is_prime(997);           // true
 * sieve.primes();                // {2, 3, 5, 7, 11, ...}
 * sieve.factorize(360);          // {{2,3}, {3,2}, {5,1}}
 */
struct Eratosthenes {
    std::vector<bool> is_prime_table;
    std::vector<int> prime_list;
    std::vector<int> min_factor;  // 最小の素因数

    explicit Eratosthenes(int n) : is_prime_table(n + 1, true), min_factor(n + 1, 0) {
        is_prime_table[0] = is_prime_table[1] = false;
        min_factor[1] = 1;

        for (int i = 2; i <= n; i++) {
            if (is_prime_table[i]) {
                prime_list.push_back(i);
                min_factor[i] = i;
                for (long long j = (long long)i * i; j <= n; j += i) {
                    is_prime_table[j] = false;
                    if (min_factor[j] == 0) min_factor[j] = i;
                }
            }
        }
    }

    bool is_prime(int n) const { return is_prime_table[n]; }

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

    /**
     * @brief 高速な素因数分解 (前処理済みの範囲内)
     * @param n 素因数分解する数
     * @return (素因数, 指数) のペアの配列
     */
    std::vector<std::pair<int, int>> factorize(int n) const {
        std::vector<std::pair<int, int>> result;
        while (n > 1) {
            int p = min_factor[n];
            int cnt = 0;
            while (min_factor[n] == p) {
                n /= p;
                cnt++;
            }
            result.emplace_back(p, cnt);
        }
        return result;
    }

    /**
     * @brief 約数列挙
     * @param n 約数を列挙する数
     * @return 約数の配列
     */
    std::vector<int> divisors(int n) const {
        std::vector<int> result = {1};
        for (auto [p, e] : factorize(n)) {
            int sz = result.size();
            int pw = 1;
            for (int i = 0; i < e; i++) {
                pw *= p;
                for (int j = 0; j < sz; j++) {
                    result.push_back(result[j] * pw);
                }
            }
        }
        return result;
    }
};

/**
 * @brief 線形篩 (各合成数を最小素因数で1回だけ篩う)
 *
 * 計算量: 厳密 O(N)
 * エラトステネスより定数倍が重いが、乗法的関数 (オイラーφ, メビウスμ) も同時に計算可能。
 *
 * @example
 * LinearSieve sieve(100000);
 * auto& primes = sieve.primes;
 * int phi_10 = sieve.phi[10];  // オイラーのφ関数
 */
struct LinearSieve {
    std::vector<int> primes;
    std::vector<int> min_factor;  // 最小素因数
    std::vector<int> phi;         // オイラーのφ関数
    std::vector<int> mobius;      // メビウス関数

    explicit LinearSieve(int n) : min_factor(n + 1, 0), phi(n + 1), mobius(n + 1) {
        phi[1] = 1;
        mobius[1] = 1;

        for (int i = 2; i <= n; i++) {
            if (min_factor[i] == 0) {
                // i は素数
                primes.push_back(i);
                min_factor[i] = i;
                phi[i] = i - 1;
                mobius[i] = -1;
            }

            for (int p : primes) {
                if ((long long)p * i > n) break;
                min_factor[p * i] = p;

                if (i % p == 0) {
                    // p は i の素因数
                    phi[p * i] = phi[i] * p;
                    mobius[p * i] = 0;
                    break;
                } else {
                    // p は i と互いに素
                    phi[p * i] = phi[i] * (p - 1);
                    mobius[p * i] = -mobius[i];
                }
            }
        }
    }

    bool is_prime(int n) const { return n >= 2 && min_factor[n] == n; }

    /**
     * @brief 高速な素因数分解
     * @param n 素因数分解する数
     * @return (素因数, 指数) のペアの配列
     */
    std::vector<std::pair<int, int>> factorize(int n) const {
        std::vector<std::pair<int, int>> result;
        while (n > 1) {
            int p = min_factor[n];
            int cnt = 0;
            while (n % p == 0) {
                n /= p;
                cnt++;
            }
            result.emplace_back(p, cnt);
        }
        return result;
    }
};

// ============================================================
// 区間篩 (Segmented Sieve)
// ============================================================

/**
 * @brief 区間篩：[L, R] 範囲の素数を列挙
 *
 * 事前に sqrt(R) までの素数を用意し、[L, R] を篩う。
 * 計算量: O(sqrt(R) + (R - L) log log R)
 *
 * @param L 下限
 * @param R 上限
 * @return [L, R] 範囲の素数の配列
 *
 * @example
 * auto primes = segment_sieve(1000000000000LL, 1000000001000LL);
 */
inline std::vector<long long> segment_sieve(long long L, long long R) {
    if (L < 2) L = 2;
    if (R < L) return {};

    // sqrt(R) までの素数を用意
    long long sqrtR = 1;
    while (sqrtR * sqrtR <= R) sqrtR++;

    Eratosthenes sieve(sqrtR);
    const auto& small_primes = sieve.primes();

    // [L, R] の篩
    std::vector<bool> is_prime(R - L + 1, true);

    for (int p : small_primes) {
        // L 以上で p の倍数である最小の数
        long long start = ((L + p - 1) / p) * p;
        if (start == p) start += p;  // p 自身は除外しない

        for (long long j = start; j <= R; j += p) {
            is_prime[j - L] = false;
        }
    }

    std::vector<long long> result;
    for (long long i = L; i <= R; i++) {
        if (is_prime[i - L]) result.push_back(i);
    }
    return result;
}

/**
 * @brief 区間篩：[L, R] の各数が素数かどうかのbool配列を返す
 * @param L 下限
 * @param R 上限
 * @return [L, R] の各数が素数かどうかの bool 配列 (インデックス0がL)
 */
inline std::vector<bool> segment_sieve_bool(long long L, long long R) {
    if (R < L) return {};

    std::vector<bool> result(R - L + 1, true);
    if (L < 2) {
        if (L == 0) {
            if (R >= 0) result[0] = false;
            if (R >= 1) result[1] = false;
        } else if (L == 1) {
            result[0] = false;
        }
    }

    long long sqrtR = 1;
    while (sqrtR * sqrtR <= R) sqrtR++;

    Eratosthenes sieve(sqrtR);
    const auto& small_primes = sieve.primes();

    for (int p : small_primes) {
        long long start = std::max(2LL, (L + p - 1) / p) * p;

        for (long long j = start; j <= R; j += p) {
            result[j - L] = false;
        }
    }

    return result;
}

/**
 * @brief [L, R] の素数の個数をカウント
 * @param L 下限
 * @param R 上限
 * @return 素数の個数
 */
inline long long count_primes_range(long long L, long long R) {
    auto primes = segment_sieve(L, R);
    return primes.size();
}

// ============================================================
// ユーティリティ
// ============================================================

/**
 * @brief 各数がいくつの互いに異なる素因数を持つかのテーブル (omega数)
 *
 * 計算量: O(N log log N)
 * 例えば 12 = 2^2 * 3 の場合、異なる素因数は 2, 3 の 2 つなので 2 を返す。
 *
 * @param n 上限
 * @return 各数iが持つ異なる素因数の個数を格納した配列 (サイズ n + 1)
 */
inline std::vector<int> distinct_prime_factor_count_table(int n) {
    if (n < 0) return {};
    std::vector<int> count(n + 1, 0);
    for (int i = 2; i <= n; i++) {
        if (count[i] == 0) {
            for (int j = i; j <= n; j += i) {
                count[j]++;
            }
        }
    }
    return count;
}

/**
 * @brief 各数がいくつの素因数を持つかのテーブル (Omega数、多重度込み)
 *
 * 計算量: O(N log log N)
 * 例えば 12 = 2^2 * 3 の場合、素因数は 2, 2, 3 の 3 つなので 3 を返す。
 *
 * @param n 上限
 * @return 各数iが持つ素因数(重複込み)の個数を格納した配列 (サイズ n + 1)
 */
inline std::vector<int> total_prime_factor_count_table(int n) {
    if (n < 0) return {};
    std::vector<int> count(n + 1, 0);
    std::vector<int> min_factor(n + 1, 0);
    for (int i = 2; i <= n; i++) {
        if (min_factor[i] == 0) {
            for (int j = i; j <= n; j += i) {
                if (min_factor[j] == 0) min_factor[j] = i;
            }
        }
        count[i] = count[i / min_factor[i]] + 1;
    }
    return count;
}

/**
 * @brief n 以下の素数の個数 (簡易版、O(N) 前処理)
 * @param n 上限
 * @return 各数i以下の素数の個数を格納した配列
 */
inline std::vector<int> prime_count_table(int n) {
    std::vector<bool> is_prime(n + 1, true);
    std::vector<int> cnt(n + 1, 0);
    is_prime[0] = is_prime[1] = false;

    for (int i = 2; i <= n; i++) {
        if (is_prime[i]) {
            for (int j = i * 2; j <= n; j += i) is_prime[j] = false;
        }
        cnt[i] = cnt[i - 1] + is_prime[i];
    }
    return cnt;
}

/**
 * @brief n のオイラーのφ関数 (単発計算用)
 * @param n 値
 * @return オイラーのφ関数値
 */
inline long long euler_phi(long long n) {
    long long result = n;
    for (long long p = 2; p * p <= n; p++) {
        if (n % p == 0) {
            while (n % p == 0) n /= p;
            result -= result / p;
        }
    }
    if (n > 1) result -= result / n;
    return result;
}

}  // namespace prime

void solve() {
    // Write your code here
    lint L, R;
    scan(L, R);
    if (L % 2 == 0) L++;
    for (lint p = L; p <= R; p += 2) {
        auto vec = prime::factorize_fast(p);
        debug(vec);
        if (ssize(vec) == 3 && vec[0].second == 2 && vec[1].second == 1 && vec[2].second == 1) {
            println("{}", p);
            return;
        }
    }
    println("{}", -1);
}

int main() {
    fast_io();
    solve();
}