/*https://twitter.com/noimi_kyopro/status/1599530868158369793?s=20&t=WGdck_EIsxY7Hc7e2sjn8g*/
#ifdef ma2
#ifdef DEBUG
#include "atcoder/my_template_debug.hpp"
#else
#include "atcoder/my_template.hpp"
#endif
#else
/*
template
ref1:https://github.com/tatyam-prime/kyopro_library
ref2:https://tatyam.hatenablog.com/entry/2019/12/15/003634
*/
#include <algorithm>
#include <array>
#include <bitset>
#include <cassert>
#include <chrono>
#include <cmath>
#include <complex>
#include <deque>
#include <forward_list>
#include <fstream>
#include <functional>
#include <iomanip>
#include <ios>
#include <iostream>
#include <limits>
#include <list>
#include <map>
#include <numeric>
#include <queue>
#include <random>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <tuple>
#include <type_traits>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <vector>
#if __has_include(<atcoder/all>)
#include <atcoder/all>
using namespace atcoder;
#endif
using namespace std;
using ll = long long;
using i128 = __int128_t;
using ld = long double;
using ull = unsigned long long;
using uint = unsigned;
using pcc = pair<char, char>;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
using pil = std::pair<int, long long>;
using pli = std::pair<long long, int>;
using pdd = pair<double, double>;
using tuplis = array<ll, 3>;
template <class T>
using pq = priority_queue<T, vector<T>, greater<T>>;
const ll LINF = 0x1fffffffffffffff;
const ll MINF = 0x7fffffffffff;
const ll LPLMT = 10000010;  // O(n)のloop上限
const ll NLGLMT =
    200010;  // O(NlogN)のloop上限（これで指定されたfor文の中にO(logN)の処理を書く）
const ll N2LMT = 3010;  // O(n^2)のloop上限
const ll N3LMT = 110;   // O(n^3)のloop上限
const ll N4LMT = 50;    // O(n^4)のloop上限
const ll TNLMT =
    20;  // O(2^n)のloop上限（実際この計算量になるのは全探索くらいなので，この値自体を使うことはなさそう）（オーダの参考程度に）
const int INF = 0x3fffffff;
const int MOD = 1000000007;
const int MODD = 998244353;
const ld DINF = numeric_limits<ld>::infinity();
const ld EPS = 1e-9;
const ld PI = 3.1415926535897932384626;  // ななみんです
const ll dx[] = {0, 1, 0, -1, 1, -1, 1, -1};
const ll dy[] = {1, 0, -1, 0, 1, 1, -1, -1};
#define NXY(nx, ny, x, y, i) \
    auto [nx, ny] = std::make_pair(x + dx[i], y + dy[i])
constexpr char DIR[] = "RDLU";

#define overload6(_1, _2, _3, _4, _5, _6, name, ...) name
#define overload4(_1, _2, _3, _4, name, ...) name
#define overload3(_1, _2, _3, name, ...) name
#define overload2(_1, _2, name, ...) name
/*繰り返し*/
#define rep1(n) for (ll i = 0; i < (n); ++i)     // n回repeat
#define rep2(i, n) for (ll i = 0; i < (n); ++i)  // n回repeat（変数指定）
#define rep3(i, a, b) for (ll i = (a); i < (b); ++i)  // a-bまでrepeat
#define rep4(i, a, b, c)      \
    for (ll i = (a); i < (b); \
         i += (c))  // a-bまで公差cでrepeat（等差数列で使えそう）
#define rep(...) \
    overload4(__VA_ARGS__, rep4, rep3, rep2, rep1)(__VA_ARGS__)  // repeatまとめ
#define rrep1(n) for (ll i = (n); i--;)
#define rrep2(i, n) for (ll i = (n); i--;)
#define rrep3(i, a, b) for (ll i = (b); i-- > (a);)
#define rrep4(i, a, b, c) \
    for (ll i = (a) + ((b) - (a)-1) / (c) * (c); i >= (a); i -= (c))
#define rrep(...)                               \
    overload4(__VA_ARGS__, rrep4, rrep3, rrep2, \
              rrep1)(__VA_ARGS__)                 // 逆repeatまとめ
#define REP1(n) for (ll i = 1; i <= (n); ++i)     // n回repeat
#define REP2(i, n) for (ll i = 1; i <= (n); ++i)  // n回repeat（変数指定）
#define REP3(i, a, b) for (ll i = (a); i <= (b); ++i)  // a-bまでrepeat
#define REP4(i, a, b, c)       \
    for (ll i = (a); i <= (b); \
         i += (c))  // a-bまで公差cでrepeat（等差数列で使えそう）
#define REP(...) \
    overload4(__VA_ARGS__, REP4, REP3, REP2, REP1)(__VA_ARGS__)  // repeatまとめ
#define RREP1(n) for (ll i = (n); i >= 1; i--)
#define RREP2(i, n) for (ll i = (n); i >= 1; i--)
#define RREP3(i, a, b) for (ll i = (b); i >= (a); i--)
#define RREP4(i, a, b, c) rrep(i, a, b + 1, c)
#define RREP(...)                               \
    overload4(__VA_ARGS__, RREP4, RREP3, RREP2, \
              RREP1)(__VA_ARGS__)  // 逆repeatまとめ
#define each1(i, a) for (auto&& i : a)
#define each2(x, y, a) for (auto&& [x, y] : a)
#define each3(x, y, z, a) for (auto&& [x, y, z] : a)
#define each4(w, x, y, z, a) for (auto&& [w, x, y, z] : a)
#define each5(v, w, x, y, z, a) for (auto&& [v, w, x, y, z] : a)
#define each(...)                                      \
    overload6(__VA_ARGS__, each5, each4, each3, each2, \
              each1)(__VA_ARGS__)  // 配列の各要素の読み出し
#define srep2(t, s) \
    for (long long t = (s); t >= 0; t = (t == 0 ? -1 : (t - 1) & (s)))
#define srep1(s) srep2(i, s)
#define srep(...) overload2(__VA_ARGS__, srep2, srep1)(__VA_ARGS__)
#define all1(i) begin(i), end(i)
#define all2(i, a) begin(i), begin(i) + a
#define all3(i, a, b) begin(i) + a, begin(i) + b
#define all(...)                       \
    overload3(__VA_ARGS__, all3, all2, \
              all1)(__VA_ARGS__)  // vectorの始めと終わりの読み取り
#define rall1(i) (i).rbegin(), (i).rend()
#define rall2(i, k) (i).rbegin(), (i).rbegin() + k
#define rall3(i, a, b) (i).rbegin() + a, (i).rbegin() + b
#define rall(...)                                \
    overload3(__VA_ARGS__, rall3, rall2, rall1)( \
        __VA_ARGS__)  // 逆イテレータの取得(rbegin：末尾,rend：頭）
#define MAX1(i, a) (i > a ? i : a)
#define MAX2(x, y, a) (x > MAX1(y, a) ? x : MAX1(y, a))
#define MAX3(x, y, z, a) (x > MAX2(y, z, a) ? x : MAX2(y, z, a))
#define MAX4(w, x, y, z, a) (w > MAX3(x, y, z, a) ? w : MAX3(x, y, z, a))
#define MAX5(v, w, x, y, z, a) \
    (v > MAX4(w, x, y, z, a) ? v : MAX4(w, x, y, z, a))
#define MAX(...)                                   \
    overload6(__VA_ARGS__, MAX5, MAX4, MAX3, MAX2, \
              MAX1)(__VA_ARGS__)  // 配列の各要素の読み出し
#define MIN1(i, a) (i < a ? i : a)
#define MIN2(x, y, a) (x < MIN1(y, a) ? x : MIN1(y, a))
#define MIN3(x, y, z, a) (x < MIN2(y, z, a) ? x : MIN2(y, z, a))
#define MIN4(w, x, y, z, a) (w < MIN3(x, y, z, a) ? w : MIN3(x, y, z, a))
#define MIN5(v, w, x, y, z, a) \
    (v < MIN4(w, x, y, z, a) ? v : MIN4(w, x, y, z, a))
#define MIN(...)                                   \
    overload6(__VA_ARGS__, MIN5, MIN4, MIN3, MIN2, \
              MIN1)(__VA_ARGS__)  // 配列の各要素の読み出し

#define vsum(...)         \
    accumulate(           \
        all(__VA_ARGS__), \
        0LL)  // vectorの合計(int形で受け付けてしまうので，小数で扱いたい場合はdsumを使う)
#define dsum(...) \
    accumulate(all(__VA_ARGS__), 0.0L)  // 小数で扱う(long long doubleなど)
#define elif else if
#define unless(a) if (!(a))
#define mp make_pair
#define mt make_tuple
/*標準入力*/
#define INT(...)     \
    int __VA_ARGS__; \
    in(__VA_ARGS__)  // int型標準入力受付，以下LDまで同様
#define LL(...)     \
    ll __VA_ARGS__; \
    in(__VA_ARGS__)
#define ULL(...)     \
    ull __VA_ARGS__; \
    in(__VA_ARGS__)
#define STR(...)        \
    string __VA_ARGS__; \
    in(__VA_ARGS__)
#define CHR(...)      \
    char __VA_ARGS__; \
    in(__VA_ARGS__)
#define DBL(...)        \
    double __VA_ARGS__; \
    in(__VA_ARGS__)
#define LD(...)     \
    ld __VA_ARGS__; \
    in(__VA_ARGS__)
/*vector操作*/
#define SORT(a) sort(all(a))  // 昇順ソート
#define RS(a)   \
    sort(       \
        all(a), \
        greater{})  // sort(vec.begin(), vec.end(), greater<ll>())//降順ソート
#define REV(a) reverse(all(a))  // 逆順
#define UNIQ(a) sort(all(a)), a.erase(unique(all(a)), end(a))
#define LROT(v, x)                        \
    std::rotate(v.begin(), v.begin() + x, \
                v.end())  // 1, 2, ..., n -> 2, ..., n, 1
#define RROT(v, x)                          \
    std::rotate(v.rbegin(), v.rbegin() + x, \
                v.rend())  // 1, 2, ..., n -> n, 1, ..., n - 1
#define CNCT(a, b) \
    a.insert(a.end(), all(b))  // vector:aの末尾にvector:bをつなぐ
#define FIND(name, val) ((name).find(val) != (name).end())
#define ALLPERM(name, func)                                            \
    {                                                                  \
        std::sort((name).begin(), (name).end());                       \
        do {                                                           \
            func                                                       \
        } while (std::next_permutation((name).begin(), (name).end())); \
    }
#define vec(type, name, ...) \
    vector<type> name(__VA_ARGS__)  // type型vectorの定義
#define VEC(type, name, size) \
    vector<type> name(size);  \
    in(name)  // type型vector(size指定)標準入力受付
#define vv(type, name, h, ...) \
    vector<vector<type>> name(h, vector<type>(__VA_ARGS__))
#define VV(type, name, h, w)                       \
    vector<vector<type>> name(h, vector<type>(w)); \
    in(name)
#define IV(type, name, size)            \
    vector<pair<type, int>> name(size); \
    for (int i = 0; i < size; i++) {    \
        type a_i;                       \
        in(a_i);                        \
        name[i] = mp(a_i, i);           \
    }  // Indexつきvector（pair型Vector,(data,index)）
#define vvv(type, name, h, w, ...)     \
    vector<vector<vector<type>>> name( \
        h, vector<vector<type>>(w, vector<type>(__VA_ARGS__)))
#define vvvv(type, name, a, b, c, ...)         \
    vector<vector<vector<vector<type>>>> name( \
        a, vector<vector<vector<type>>>(       \
               b, vector<vector<type>>(c, vector<type>(__VA_ARGS__))))
#define TRYDFS(dfs)   \
    try {             \
        dfs;          \
    } catch (int e) { \
        return 0;     \
    }
template <class T>
auto vmin(const T& a) {
    return *min_element(all(a));
}
template <class T>
auto vmax(const T& a) {
    return *max_element(all(a));
}
inline long long popcnt(unsigned long long a) {
    return __builtin_popcountll(a);
}
/*https://maspypy.github.io/library/my_template.hpp*/
// (0, 1, 2, 3, 4) -> (-1, 0, 1, 1, 2)
int tbit(int x) { return (x == 0 ? -1 : 31 - __builtin_clz(x)); }
int tbit(unsigned x) { return (x == 0 ? -1 : 31 - __builtin_clz(x)); }
int tbit(long long x) { return (x == 0 ? -1 : 63 - __builtin_clzll(x)); }
int tbit(unsigned long long x) {
    return (x == 0 ? -1 : 63 - __builtin_clzll(x));
}
// (0, 1, 2, 3, 4) -> (-1, 0, 1, 0, 2)
int lbit(int x) { return (x == 0 ? -1 : __builtin_ctz(x)); }
int lbit(unsigned x) { return (x == 0 ? -1 : __builtin_ctz(x)); }
int lbit(long long x) { return (x == 0 ? -1 : __builtin_ctzll(x)); }
int lbit(unsigned long long x) { return (x == 0 ? -1 : __builtin_ctzll(x)); }
bool ispow2(int i) { return i && (i & -i) == i; }
ll gcd(ll a, ll b) {
    while (b) {
        ll c = b;
        b = a % b;
        a = c;
    }
    return a;
}
ll lcm(ll a, ll b) {
    if (!a || !b) return 0;
    return a * b / gcd(a, b);
}
ll intpow(ll a, ll b) {
    ll ans = 1;
    while (b) {
        if (b & 1) ans *= a;
        a *= a;
        b /= 2;
    }
    return ans;
}
ll modpow(ll a, ll b, ll p) {
    if (a >= p) a %= p;
    ll ans = 1;
    while (b) {
        if (b & 1) (ans *= a) %= p;
        (a *= a) %= p;
        b /= 2;
    }
    return ans;
}
template <class T, class S>
decltype(T() / S()) CEIL(T x, S y) {
    assert(y != 0);
    return (y < 0 ? CEIL(-x, -y) : (x > 0 ? (x + y - 1) / y : x / y));
}

template <class T, class S>
decltype(T() / S()) FLOOR(T x, S y) {
    assert(y != 0);
    return (y < 0 ? FLOOR(-x, -y)
                  : (x > 0 ? x / y : x / y - (x % y == 0 ? 0 : 1)));
}
/*ref: https://hitonanode.github.io/cplib-cpp/utilities/rotate90.hpp*/
template <typename T>
std::vector<std::vector<T>> rot90(const std::vector<std::vector<T>>& in) {
    const int H = in.size(), W = in[0].size();
    std::vector<std::vector<T>> ret(W, std::vector<T>(H));
    for (int i = 0; i < H; i++) {
        for (int j = 0; j < W; j++) ret[j][i] = in[i][W - 1 - j];
    }
    return ret;
}

std::vector<std::string> rot90(const std::vector<std::string>& in) {
    const int H = in.size(), W = in[0].size();
    std::vector<std::string> ret(W, std::string(H, '\0'));
    for (int i = 0; i < H; i++) {
        for (int j = 0; j < W; j++) ret[j][i] = in[i][W - 1 - j];
    }
    return ret;
}

template <typename T>
int LIS(std::vector<T>& v) {
    int res = 0;
    const T MAX_VALUE =
        typeid(T) == typeid(int) ? 0x3fffffff : 0x1fffffffffffffff;
    std::vector<T> mn(v.size() + 1, MAX_VALUE);
    mn.front() = -MAX_VALUE;
    for (const T& x : v) {
        const int id = std::lower_bound(mn.begin(), mn.end(), x) - mn.begin();
        mn[id] = x;
        if (res < id) res = id;
    }
    return res;
}
template <class T, class U>
bool chmin(T& a, const U& b) {
    if (a > b) {
        a = b;
        return 1;
    }
    return 0;
}
template <class T, class U>
bool chmax(T& a, const U& b) {
    if (a < b) {
        a = b;
        return 1;
    }
    return 0;
}
template <class T, class U, class F, class V = decltype(T() + U())>
V bins(const T OK, const U NG, const F& judge, const double allowError = 1e-9,
       int iter = 100) {
    assert(judge(OK));
    // assert(not judge(NG));
    auto islr = [allowError](V ok, V ng) -> bool {
        if (typeid(V) == typeid(double) or typeid(V) == typeid(long double)) {
            return std::abs(ok - ng) > allowError;
        }
        return std::abs(ok - ng) > 1;
    };
    V ok = OK, ng = NG;
    for (V mid = ng + (ok - ng) / 2; islr(ok, ng) and iter-- > 0;
         mid = ng + (ok - ng) / 2) {
        if (judge(mid))
            ok = mid;
        else
            ng = mid;
    }
    return ok;
}
template <typename T>
std::vector<std::pair<T, int>> RLE(const std::vector<T>& S) {
    std::vector<std::pair<T, int>> res;
    for (const T& c : S) {
        if (res.empty() or res.back().first != c) {
            res.emplace_back(c, 1);
        } else {
            res.back().second++;
        }
    }
    return res;
}
std::vector<std::pair<char, int>> RLE(const std::string& S) {
    std::vector<std::pair<char, int>> res;
    for (const char& c : S) {
        if (res.empty() or res.back().first != c) {
            res.emplace_back(c, 1);
        } else {
            res.back().second++;
        }
    }
    return res;
}
void af() { assert(false); }
vector<ll> iota(ll n) {
    vector<ll> a(n);
    iota(a.begin(), a.end(), 0);
    return a;
}  // 0~n-1まで順に入れられたvectorを生成
vector<pll> factor(ull x) {
    vector<pll> ans;
    for (ull i = 2; i * i <= x; i++)
        if (x % i == 0) {
            ans.push_back({i, 1});
            while ((x /= i) % i == 0) ans.back().second++;
        }
    if (x != 1) ans.push_back({x, 1});
    return ans;
}  // xの素因数分解{素因数，何個あるか}のvectorを返す
map<ll, ll> factor_map(ull x) {
    map<ll, ll> ans;
    for (ull i = 2; i * i <= x; i++)
        if (x % i == 0) {
            ans[i] = 1;
            while ((x /= i) % i == 0) ans[i]++;
        }
    if (x != 1) ans[x] = 1;
    return ans;
}  // 素因数分解mapVer.キー：素因数，要素＝その個数
vector<ll> divisor(ull x) {
    vector<ll> ans;
    for (ull i = 1; i * i <= x; i++)
        if (x % i == 0) ans.push_back(i);
    rrep(ans.size() - (ans.back() * ans.back() == x)) ans.push_back(x / ans[i]);
    return ans;
}  // 約数が昇順に格納されたvectorを返す
template <class T>
unordered_map<T, ll> press(vector<T>& a) {
    auto b = a;
    sort(all(b));
    b.erase(unique(all(b)), b.end());
    unordered_map<T, ll> ans;
    rep(b.size()) ans[b[i]] = i;
    // each(i, a) i = ans[i];
    return ans;
}  // 圧縮　aの各要素をa内の要素で見た時に昇順で何番目だったかの情報に置き換える，{要素，何番目}を表すunordered_mapを返す
template <class T>
map<T, ll> press_map(vector<T>& a) {
    auto b = a;
    sort(all(b));
    b.erase(unique(all(b)), b.end());
    map<T, ll> ans;
    rep(b.size()) ans[b[i]] = i;
    // each(i, a) i = ans[i];
    return ans;
}  // 圧縮mapVer.
/*https://github.com/atcoder/ac-library/blob/d8ca7f26686f6c78d15d13ca438ea866526e87fb/atcoder/internal_queue.hpp*/
template <class T>
struct QUE {
    std::vector<T> payload;
    int pos = 0;
    void reserve(int n) { payload.reserve(n); }
    int size() const { return int(payload.size()) - pos; }
    bool empty() const { return pos == int(payload.size()); }
    void push(const T& t) { payload.push_back(t); }
    template <class... Args>
    decltype(auto) emplace(Args&&... args) {
        payload.emplace_back(args...);
    }
    T& front() { return payload[pos]; }
    void clear() {
        payload.clear();
        pos = 0;
    }
    void pop() { pos++; }
};
int scan() { return getchar(); }
void scan(int& a) { scanf("%d", &a); }
void scan(unsigned& a) { scanf("%u", &a); }
void scan(long& a) { scanf("%ld", &a); }
void scan(long long& a) { scanf("%lld", &a); }
void scan(unsigned long long& a) { scanf("%llu", &a); }
void scan(char& a) {
    do {
        a = getchar();
    } while (a == ' ' || a == '\n');
}
void scan(float& a) { scanf("%f", &a); }
void scan(double& a) { scanf("%lf", &a); }
void scan(long double& a) { scanf("%Lf", &a); }
void scan(vector<bool>& a) {
    for (unsigned i = 0; i < a.size(); i++) {
        int b;
        scan(b);
        a[i] = b;
    }
}
void scan(char a[]) { scanf("%s", a); }
void scan(string& a) { cin >> a; }
template <class T>
void scan(vector<T>&);
template <class T, size_t size>
void scan(array<T, size>&);
template <class T, class L>
void scan(pair<T, L>&);
template <class T, size_t size>
void scan(T (&)[size]);
template <class T>
void scan(vector<T>& a) {
    for (auto&& i : a) scan(i);
}
template <class T>
void scan(deque<T>& a) {
    for (auto&& i : a) scan(i);
}
template <class T, size_t size>
void scan(array<T, size>& a) {
    for (auto&& i : a) scan(i);
}
template <class T, class L>
void scan(pair<T, L>& p) {
    scan(p.first);
    scan(p.second);
}
template <class T, size_t size>
void scan(T (&a)[size]) {
    for (auto&& i : a) scan(i);
}
template <class T>
void scan(T& a) {
    cin >> a;
}
void in() {}
template <class Head, class... Tail>
void in(Head& head, Tail&... tail) {
    scan(head);
    in(tail...);
}
void print() { putchar(' '); }
void print(bool a) { printf("%d", a); }
void print(int a) { printf("%d", a); }
void print(unsigned a) { printf("%u", a); }
void print(long a) { printf("%ld", a); }
void print(long long a) { printf("%lld", a); }
void print(unsigned long long a) { printf("%llu", a); }
void print(char a) { printf("%c", a); }
void print(char a[]) { printf("%s", a); }
void print(const char a[]) { printf("%s", a); }
void print(float a) { printf("%.15f", a); }
void print(double a) { printf("%.15f", a); }
void print(long double a) { printf("%.15Lf", a); }
void print(const string& a) {
    for (auto&& i : a) print(i);
}
#if __has_include(<atcoder/all>)
template <int m>
void print(const atcoder::static_modint<m>& a) {
    printf("%d", a.val());
}

template <int m>
void print(const atcoder::dynamic_modint<m>& a) {
    printf("%d", a.val());
}
#endif
template <class T>
void print(const vector<T>&);
template <class T, size_t size>
void print(const array<T, size>&);
template <class T, class L>
void print(const pair<T, L>& p);
template <class T, size_t size>
void print(const T (&)[size]);
template <class T>
void print(const vector<T>& a) {
    if (a.empty()) return;
    print(a[0]);
    for (auto i = a.begin(); ++i != a.end();) {
        putchar(' ');
        print(*i);
    }
}
template <class T>
void print(const deque<T>& a) {
    if (a.empty()) return;
    print(a[0]);
    for (auto i = a.begin(); ++i != a.end();) {
        putchar(' ');
        print(*i);
    }
}
template <class T, size_t size>
void print(const array<T, size>& a) {
    print(a[0]);
    for (auto i = a.begin(); ++i != a.end();) {
        putchar(' ');
        print(*i);
    }
}
template <class T, class L>
void print(const pair<T, L>& p) {
    print(p.first);
    putchar(' ');
    print(p.second);
}
template <class T, size_t size>
void print(const T (&a)[size]) {
    print(a[0]);
    for (auto i = a; ++i != end(a);) {
        putchar(' ');
        print(*i);
    }
}
template <class T>
void print(const std::set<T>& a) {
    if (a.empty()) return;
    print(*a.begin());
    for (auto i = a.begin(); ++i != a.end();) {
        putchar(' ');
        print(*i);
    }
}
template <class T>
void print(const std::multiset<T>& a) {
    if (a.empty()) return;
    print(*a.begin());
    for (auto i = a.begin(); ++i != a.end();) {
        putchar(' ');
        print(*i);
    }
}
template <class T>
void print(const QUE<T>& a) {
    if (a.empty()) return;
    print(a.payload[a.pos]);
    for (auto i = a.payload.begin() + a.pos; ++i != a.payload.end();) {
        putchar(' ');
        print(*i);
    }
}
template <class T>
void print(const T& a) {
    cout << a;
}
int out() {
    putchar('\n');
    return 0;
}
template <class T>
int out(const T& t) {
    print(t);
    putchar('\n');
    return 0;
}  // cout<<t<<endl
template <class Head, class... Tail>
int out(const Head& head, const Tail&... tail) {
    print(head);
    putchar(' ');
    out(tail...);
    return 0;
}
#ifdef DEBUG
inline ll __lg(ull __n) {
    return sizeof(ull) * __CHAR_BIT__ - 1 - __builtin_clzll(__n);
}
#define debug(...)           \
    {                        \
        print(#__VA_ARGS__); \
        print(":");          \
        out(__VA_ARGS__);    \
    }
#else
#define debug(...) void(0)
#endif

#define ASK(...)               \
    {                          \
        out('?', __VA_ARGS__); \
        fflush(stdout);        \
    }
#define ANS(...)               \
    {                          \
        out('!', __VA_ARGS__); \
        fflush(stdout);        \
    }

/*判定出力*/
int dame() { return out(-1); }
int Win(bool i = true) {
    return out(i ? "Win" : "Lose");
}  // iがfirstか判断，以下同様
int Lose() { return out("Lose"); }  // iがfirstか判断，以下同様
int Alice(bool i = true) {
    return out(i ? "Alice" : "Bob");
}  // iがfirstか判断，以下同様
int Bob() { return out("Bob"); }  // iがfirstか判断，以下同様
int Takahashi(bool i = true) {
    return out(i ? "Takahashi" : "Aoki");
}  // iがfirstか判断，以下同様
int Aoki() { return out("Aoki"); }  // iがfirstか判断，以下同様
int first(bool i = true) {
    return out(i ? "first" : "second");
}  // iがfirstか判断，以下同様
int second() { return out("second"); }  // iがfirstか判断，以下同様
int First(bool i = true) {
    return out(i ? "First" : "Second");
}  // iがfirstか判断，以下同様
int Second() { return out("Second"); }  // iがfirstか判断，以下同様
int yes(bool i = true) { return out(i ? "yes" : "no"); }
int no() { return out("no"); }
int Yes(bool i = true) { return out(i ? "Yes" : "No"); }
int No() { return out("No"); }
int YES(bool i = true) { return out(i ? "YES" : "NO"); }
int NO() { return out("NO"); }
int Yay(bool i = true) { return out(i ? "Yay!" : ":("); }
int possible(bool i = true) { return out(i ? "possible" : "impossible"); }
int impossible() { return out("impossible"); }
int Possible(bool i = true) { return out(i ? "Possible" : "Impossible"); }
int Impossible() { return out("Impossible"); }
int POSSIBLE(bool i = true) { return out(i ? "POSSIBLE" : "IMPOSSIBLE"); }
int IMPOSSIBLE() { return out("IMPOSSIBLE"); }
void Case(ll i) { printf("Case #%lld: ", i); }

void infprint(int x) { return print(x == INF ? -1 : x); }
void infprint(const std::vector<int>& a) {
    if (a.empty()) return;
    infprint(a[0]);
    for (auto i = a.begin(); ++i != a.end();) {
        putchar(' ');
        infprint(*i);
    }
}
int INFOUT() {
    putchar('\n');
    return 0;
}
template <class T>
int INFOUT(const T& t) {
    infprint(t);
    putchar('\n');
    return 0;
}  // cout<<t<<endl
template <class Head, class... Tail>
int INFOUT(const Head& head, const Tail&... tail) {
    infprint(head);
    putchar(' ');
    INFOUT(tail...);
    return 0;
}

void linfprint(long long x) { return print(x == LINF ? -1 : x); }
void linfprint(const std::vector<long long>& a) {
    if (a.empty()) return;
    linfprint(a[0]);
    for (auto i = a.begin(); ++i != a.end();) {
        putchar(' ');
        linfprint(*i);
    }
}
int LINFOUT() {
    putchar('\n');
    return 0;
}
template <class T>
int LINFOUT(const T& t) {
    linfprint(t);
    putchar('\n');
    return 0;
}  // cout<<t<<endl
template <class Head, class... Tail>
int LINFOUT(const Head& head, const Tail&... tail) {
    linfprint(head);
    putchar(' ');
    LINFOUT(tail...);
    return 0;
}

template <typename T, typename U, typename V>
bool EE(T i, U j, V k) {
    return i <= j and j <= k;
}
template <typename T, typename U, typename V>
bool CE(T i, U j, V k) {
    return i < j and j <= k;
}
template <typename T, typename U, typename V>
bool EC(T i, U j, V k) {
    return i <= j and j < k;
}
template <typename T, typename U, typename V>
bool CC(T i, U j, V k) {
    return i < j and j < k;
}
/*vector探索*/
template <typename T>
T pick(QUE<T>& que) {
    assert(not que.empty());
    const T x = que.front();
    que.pop();
    return x;
}

template <typename T>
T pick_front(std::deque<T>& que) {
    assert(not que.empty());
    const T x = que.front();
    que.pop_front();
    return x;
}

template <typename T>
T pick_back(std::deque<T>& que) {
    assert(not que.empty());
    const T x = que.back();
    que.pop_back();
    return x;
}

template <typename T>
T pick(std::queue<T>& que) {
    assert(not que.empty());
    const T x = que.front();
    que.pop();
    return x;
}

template <typename T>
T pick(std::priority_queue<T>& que) {
    assert(not que.empty());
    const T x = que.top();
    que.pop();
    return x;
}

template <typename T>
T pick(std::priority_queue<T, std::vector<T>, std::greater<T>>& que) {
    assert(not que.empty());
    const T x = que.top();
    que.pop();
    return x;
}

template <typename T>
T pick(std::vector<T>& que) {
    assert(not que.empty());
    const T x = que.back();
    que.pop_back();
    return x;
}

template <typename T>
T pick(std::stack<T>& que) {
    assert(not que.empty());
    const T x = que.top();
    que.pop();
    return x;
}

char pick(std::string& que) {
    assert(not que.empty());
    const char x = que.back();
    que.pop_back();
    return x;
}

#define CNT(v, k) \
    count(all(v), k)  // 配列vの中で要素kが何個あるかを返す(size_t)
#define CNTIF(v, l) \
    count_if(       \
        all(v),     \
        l)  // 配列vの中で条件式(lambda式)を満たす個数を返す(ex.int num =
            //  count_if(v.begin(), v.end(), [](int i){return i % 3 == 0;});)
#define SORT2D(myVec, i)                                       \
    sort(myVec.begin(), myVec.end(),                           \
         [](const vector<ll>& alpha, const vector<ll>& beta) { \
             return alpha[i] < beta[i];                        \
         });  // i列めでソート
/*最大公約数*/
template <class T>
T vgcd(T m, T n) {
    return gcd(m, n);
}

template <class T, class... Args>
T vgcd(T a, Args... args) {
    return vgcd(a, vgcd(args...));
}

#define vecgcd(a) reduce(all(a), 0LL, gcd<ll, ll>)
/*あまり（強制的に正の余りを出力）*/
template <class T, class U>
void mod(T& n, const U p) {
    assert(p > 0);
    if (0 <= n and n < p) return;
    if (n == p or p == 1) {
        n = 0;
    } else if (p == 2) {
        n &= 1;
    } else if (abs(n) <= p) {
        n = p + n;
    } else {
        n %= p;
        if (n < 0) n += p;
    }
}
template <class T, class U>
T rtmod(T n, const U p) {
    mod(n, p);
    return n;
}
/*逆元　あまりの割り算をするときにこいつをかける(a/b→a*modinv(b))*/
// mod. m での a の逆元 a^{-1} を計算する
ll modinv(ll a, ll m) {
    long long b = m, u = 1, v = 0;
    while (b) {
        long long t = a / b;
        a -= t * b;
        swap(a, b);
        u -= t * v;
        swap(u, v);
    }
    u %= m;
    if (u < 0) u += m;
    return u;
}
/*階乗*/
ll fac2(ll k, ll a, ll p) {
    ll sum = 1;
    for (ll i = k; i > k - a; --i) {
        sum *= i;
        sum %= p;  // あまりを出力せよ問題の時はこれもやる
    }
    return sum;
}
/*組み合わせnCk*/
ll modcomb(ll n, ll k, ll p) {
    ll c = fac2(n, k, p);
    c *= modinv(fac2(k, k, p), p);
    mod(c, p);
    return c;
}
/*ダブリング*/
/*
参考：http://satanic0258.hatenablog.com/entry/2017/02/23/222647

使える場所：1回遷移した先が明確にわかる時

目的：
・ある数XのQ乗を求める
・根付き木において、ある頂点vのQ個上の親を知る
・ある地点からQ回進んだ先を求める
*/
// int N; // 全体の要素数
// int Q;//試行回数
ll doubling(
    const ll N, const ll Q,
    vector<ll>& a) {  // cin>>N>>Q;//標準入力から要素数と試行回数を受け取る場合
    ll LOG_Q = floor(log2(Q)) + 1;

    // next[k][i]で、i番目の要素の「2^k個次の要素」を指す
    // (なお、i番目の要素に対して「2^k個次の要素」が存在しないとき、
    //  next[k][i]が指し示す要素番号を-1とします)
    std::vector<std::vector<ll>> next(LOG_Q + 1, std::vector<ll>(N));
    // ll a[N];//各要素の次の行き先

    // next[0]を計算
    for (int i = 0; i < N; ++i) {
        next[0][i] = a[i];
    }

    // nextを計算
    for (ll k = 0; k < LOG_Q; ++k) {
        for (int i = 0; i < N; ++i) {
            if (next[k][i] == -1) {
                // 2^k個次に要素が無い時、当然2^(k+1)個次にも要素はありません
                next[k + 1][i] = -1;
            } else {
                // 「2^k個次の要素」の2^k個次の要素は、2^(k+1)個次の要素です
                next[k + 1][i] = next[k][next[k][i]];
            }
        }
    }

    // ----ここまで準備----

    // p番目の要素の「Q個次の要素」を求めることを考えます
    ll p = 0;
    for (ll k = LOG_Q - 1; k >= 0; --k) {
        if (p == -1) {
            // pがすでに存在しない要素を指していたら、
            // それ以降で存在する要素を指すことはないためループを抜けます
            break;
        }
        if ((Q >> k) & 1) {  // ex(Q=5)5=101(2)であり，2^2+2^0回進むことを表す
            // Qを二進展開した際、k番目のビットが立っていたら、
            // pの位置を2^kだけ次にずらします
            p = next[k][p];
        }
    }
    return p;  // ここでのpが最終的な答えになる
}
/*素数判定*/
bool IsPrime(ll num) {
    if (num < 2)
        return false;
    else if (num == 2)
        return true;
    else if (num % 2 == 0)
        return false;  // 偶数はあらかじめ除く

    double sqrtNum = sqrt(num);
    for (int i = 3; i <= sqrtNum; i += 2) {
        if (num % i == 0) {
            // 素数ではない
            return false;
        }
    }

    // 素数である
    return true;
}
/*https://twitter.com/noshi91/status/1366018159178735625*/
template <int N>
struct nreparray {
    std::array<int, N> v;
    nreparray(std::array<int, N> v_) : v(v_) {}
    struct nrepitr {
        const std::array<int, N>& v;
        std::array<int, N> tmp;
        bool is_end;
        nrepitr(const std::array<int, N>& v_) : v(v_), tmp(), is_end(false) {}
        bool operator!=(const nrepitr&) const { return !is_end; }
        void operator++() {
            int pos = N - 1;
            while (pos != -1) {
                tmp[pos] += 1;
                if (tmp[pos] == v[pos]) {
                    tmp[pos] = 0;
                    pos -= 1;
                } else {
                    break;
                }
            }
            if (pos == -1) {
                is_end = true;
            }
        }
        const std::array<int, N>& operator*() const { return tmp; }
    };
    nrepitr begin() const { return nrepitr(v); }
    nrepitr end() const { return nrepitr(v); }
};

struct nrepvector {
    std::vector<int> v;
    nrepvector(std::vector<int> v_) : v(v_) {}
    struct nrepitr {
        const std::vector<int>& v;
        std::vector<int> tmp;
        bool is_end;
        nrepitr(const std::vector<int>& v_)
            : v(v_), tmp(v.size(), 0), is_end(false) {}
        bool operator!=(const nrepitr&) const { return !is_end; }
        void operator++() {
            int pos = v.size() - 1;
            while (pos != -1) {
                tmp[pos] += 1;
                if (tmp[pos] == v[pos]) {
                    tmp[pos] = 0;
                    pos -= 1;
                } else {
                    break;
                }
            }
            if (pos == -1) {
                is_end = true;
            }
        }
        const std::vector<int>& operator*() const { return tmp; }
    };
    nrepitr begin() const { return nrepitr(v); }
    nrepitr end() const { return nrepitr(v); }
};

auto nrep(std::vector<int> v) { return nrepvector(v); }
template <class... Ts>
auto nrep(Ts... v) {
    return nreparray<std::tuple_size<std::tuple<Ts...>>::value>({v...});
}

mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
long long rnd(long long B = 1) {
    return B == 1 ? rng() : (unsigned long long)rng() % B;
}
/*ページのソースを表示->command+F->問題文　で問題文コピペする

*/
/*
0~n-1までの順列の出力
rep(n)v.push_back(i);
do{}while(next_permutation(all(v)));
*/
// ceil()//切り上げ　ll(ceil((ld)n/(ld)x))=(n+x-1)/x（整数除算）なのでそっちがいいかも
// floor()//切り捨て
// round()//四捨五入
// deque<ll> deq;//両端キュー使う，先頭と末尾へのアクセスが早い
// using std::map;
// map<string,ll>memo;//<キー，その要素＞，キーの検索が早い，キーは昇順にソートされる
#endif
/*以下コーディング*/
void preprocess();
signed solve();
void run_testcase();

signed main() {
    preprocess();

    signed testcase = 1;
    scanf("%d", &testcase);//テストケース数を渡す

    for (int ti = 1; ti <= testcase; ti++) {
        // Case(ti);
        run_testcase();
    }
}

void run_testcase() {  // 入力と解法を分離させるだけなので，基本的に入力以外何も書かない
    // Input(面倒なときに分離させる)
    solve();  // 実装本体はこっちに書く（必要に応じて引数を渡す）
}

void preprocess() {}

signed solve() {  // main
    /*
    idea:
    */
    // 問題タイトルとサンプル　読め！！！！！！！！！！！！！！！
    LD(p);
    INT(k);

    ld ans = 0;
    ld now = 1;
    REP(t, k - 1) {
        ans += t * now * p;
        now *= 1 - p;
    }
    ans += k * now;
    out(ans);
    return 0;  // checklist.txtを確認
}