#include <algorithm>
#include <bit>
#include <bitset>
#include <cassert>
#include <complex>
#include <climits>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <deque>
#include <iostream>
#include <map>
#include <iomanip>
#include <optional>
#include <random>
#include <ranges>
#include <unordered_set>
#include <unordered_map>
#include <vector>
#include <set>
#include <string>
#include <type_traits>
#include <variant>

using std::__gcd;
using std::bitset;
using std::cin;
using std::cerr;
using std::complex;
using std::cout;
using std::deque;
using std::endl;
using std::greater;
using std::hash;
using std::istream;
using std::min;
using std::map;
using std::max;
using std::multiset;
using std::nullopt;
using std::optional;
using std::ostream;
using std::pair;
using std::rotate;
using std::set;
using std::setprecision;
using std::string;
using std::string_view;
using std::swap;
using std::tie;
using std::to_string;
using std::tuple;
using std::unordered_map;
using std::unordered_set;
using std::vector;

#if __cplusplus >= 201709L
  using std::ranges::sort;
  using std::ranges::views::iota;
  using std::views::reverse;
  using std::views::filter;
  using std::views::transform;
#endif

#define L(expr) ([&](const auto& _) { return (expr) ; })
#define Map(expr) (transform((L((expr)))))
#define Filter(expr) (filter((L((expr)))))

template <typename T>
ostream& operator<< (ostream& o, const multiset<T>& v) {
 for (const auto& x : v) o << x << " ";
 return o;
}

template <typename T>
ostream& operator<< (ostream& o, const unordered_set<T>& v) {
 o << "{";
 for (const auto& x : v) o << x << " ";
 o << "}";
 return o;
}

template<typename T, typename U>
ostream& operator<< (ostream& o, const pair<T, U>& p) {
  o << "<" << p.first << ", " << p.second << ">";
  return o;
}

template <typename T>
ostream& operator<< (ostream& o, const vector<T>& v) {
 for (const auto& x : v) o << x << " ";
 return o;
}

template <typename T>
ostream& operator<< (ostream& o, const set<T>& v) {
 for (const auto& x : v) o << x << " ";
 return o;
}

template <typename T>
ostream& operator<< (ostream& o, const deque<T>& v) {
 for (const auto& x : v) o << x << " ";
 return o;
}

template <typename K, typename V>
ostream& operator<<(ostream& o, const unordered_map<K, V>& m) {
  o << "{";
  for (const auto& [k, v] : m)
    o << " " << k << ": " << v << ",";
  o << "}";
  return o;
}

template <typename K, typename V>
ostream& operator<<(ostream& o, const map<K, V>& m) {
  o << "{";
  for (const auto& [k, v] : m)
    o << " " << k << ": " << v << ",";
  o << "}";
  return o;
}

template <typename T>
ostream& operator<< (ostream& o, const vector<vector<T>>& v) {
 for (const auto& x : v) o << x << endl;
 return o;
}

ostream& operator<< (ostream& o, const vector<string>& v) {
 for (const auto& x : v) o << x << endl;
 return o;
}

void print_to(ostream& o) {
  o << endl;
};

template <typename T, typename... A>
void print_to(ostream& o, const T& t, const A&... a) {
  o << t << " ";
  print_to(o, a...);
}

template <typename... A>
void out(const A&... a) {
  print_to(cout, a...); 
}

template <typename T, typename... A>
const T& cerr_and_return(const T& t, const A&... a) {
  print_to(cerr, "\t", t, "  ←   ", a...);
  return t;
}

template <typename T, typename... A>
T& cerr_and_return(T& t, const A&... a) {
  print_to(cerr, "\t", t, "  ←   ", a...);
  return t;
}

#ifdef DEBUG
  #define err(...) print_to(cerr, "\t[", #__VA_ARGS__, "]", " = ", __VA_ARGS__)
#else
  #define err(...)
#endif

#ifdef DEBUG
  #define E(expr) (cerr_and_return((expr), (#expr)))
#else
  #define E(expr) (expr)
#endif

class in {
 public:
  in() {}
  in(istream &i) : i(i) {}
  in(int n) : n(n) {}

  template <typename T>
  operator T () {
    T n;
    i >> n;
    return n;
  }
  
  template <typename T>
  operator deque<T> () {
    deque<T> v(n ? n.value() : static_cast<int>(*this));
    for (auto& x : v) x = *this;
    return v;
  }
  
  template <typename T>
  operator multiset<T> () {
    return insert<multiset<T>>(n ? n.value() : static_cast<int>(*this));
  }
  
  template <typename T, typename U>
  operator pair<T, U> () {
    return {*this, *this};
  }

  template <typename T>
  operator set<T> () {
    return insert<set<T>>(n ? n.value() : static_cast<int>(*this));
  }
  
  template <typename T>
  operator vector<T> () {
    vector<T> v(n ? n.value() : static_cast<int>(*this));
    for (auto& x : v) x = static_cast<T>(*this);
    return v;
  }
  
 private:
  template <typename S>
  S insert(int n) {
    S s;
    while (n--) s.insert(static_cast<typename S::key_type>(*this));
    return s;
  }
  
  optional<int> n;
  istream& i = cin;
} _;

/*
template <typename T>
istream& operator>> (istream& i, T& t) {
  t = static_cast<T>(in(i));
  return i;
}
*/

template <typename U, typename V>
pair<U, V> operator += (pair<U, V>& p, const pair<U, V>& q) {
  p.first += q.first;
  p.second += q.second;
  return p;
}

template <typename U, typename V>
pair<U, V> operator + (pair<U, V> p, const pair<U, V>& q) {
  return p += q;
}

template <typename U, typename V>
pair<U, V> operator -= (pair<U, V>& p, const pair<U, V>& q) {
  p.first -= q.first;
  p.second -= q.second;
  return p;
}

template <typename U, typename V>
pair<U, V> operator - (pair<U, V> p, const pair<U, V>& q) {
  return p -= q;
}

template <typename U, typename V>
pair<U, V> operator *= (pair<U, V>& p, const pair<U, V>& q) {
  U new_first = p.first * q.first - p.second * q.second;
  V new_second = p.first * q.second + p.second * q.first;
  p.first = new_first;
  p.second = new_second;
  return p;
}

template <typename U, typename V>
double hypot(const pair<U, V>& p) {
  return hypot(1.0 * p.first, 1.0 * p.second);
}

template <typename U, typename V>
struct std::hash<pair<U, V>> {
  std::size_t operator () (const pair<U, V>& p) const {
    return hash<U>{}(p.first) ^ (hash<V>{}(p.second) << 1); // https://en.cppreference.com/w/cpp/utility/hash 
  }
};

template <typename Element, typename... List>
struct Contains {
  static constexpr bool value = false;
};

template <typename Element, typename... List>
struct Contains<Element, Element, List...> {
  static constexpr bool value = true;
};

template <typename Element, typename Other, typename... List>
struct Contains<Element, Other, List...> {
  static constexpr bool value = Contains<Element, List...>::value;
};

template <typename... Args>
inline constexpr bool contains_v = Contains<Args...>::value;

struct Empty {};

#define TREE_SUM
#define TREE_MULTIPLY

template <typename V = long long>
struct FastTree {
  using K = long long;
  const K a = -1e18, b = 1e18;
  
  struct Node {
    Node *left = nullptr, *right = nullptr;
    V value = 0;
    #ifdef TREE_SUM
      V sum_ = 0;
    #endif
    
    #ifdef TREE_MULTIPLY
      V multiplier = 1;
    #endif
    
    deque<string> to_lines(K a, K b) const {
      const K m = a + (b - a + 1) / 2 - 1;
      
      deque<string> lines = left ? left->to_lines(a, m) : deque<string>{};
      
      if (right) {
        deque<string> right_lines = right->to_lines(m + 1, b);
        
        size_t pad = 0;
        for (string_view l : lines) pad = max(pad, l.size());
        for (string& l : lines) l += string(pad - l.size(), ' ') + ']';
      
        while (lines.size() < right_lines.size())
          lines.push_back(string(pad + !!pad, ' '));
        
        for (int i = 0; i < right_lines.size(); ++i)
         lines[i] += right_lines[i];
      }
      
      lines.push_front("[" + to_string(a) + " " + to_string(b));
      if (value != 0) lines[0] += (value >= 0 ? " +" : " ") + to_string(value);
      #ifdef TREE_MULTIPLY
        if (multiplier != 1) lines[0] += " *" + to_string(multiplier);
      #endif
      #ifdef TREE_SUM
        lines[0] += " s=" + to_string(sum_);
      #endif
          
      return lines; 
    }
  } root;
  
  V operator[] (const K k) const {
    if (k < a || b < k) return 0;
    K a = this->a, b = this->b, m;
    const Node* node = &root;
    V r = 0;
    while (node) {
      r += node->value;
      m = a + (b - a + 1) / 2 - 1; 
      if (k <= m) {
        b = m;
        node = node->left;
      } else {
        a = m + 1;
        node = node->right;
      }
    }
    return r;
  }

  #ifdef TREE_SUM
  V sum(const K l, const K r) const {
    static vector<tuple<K, K, const Node*
    #ifdef TREE_MULTIPLY
      , V
    #endif
    >> stack(128);
    int top = 0;
    stack[top] = {a, b, &root
    #ifdef TREE_MULTIPLY
      , 1
    #endif
    };
    K a, b, m;
    const Node* node;
    #ifdef TREE_MULTIPLY
      V multiplier;
    #endif
    V s = 0;
    while (top >= 0) {
      tie(a, b, node
      #ifdef TREE_MULTIPLY
        , multiplier
      #endif
      ) = stack[top--];
      if (l <= a && b <= r) s +=
        #ifdef TREE_MULTIPLY
          multiplier *
        #endif
        node->sum_;
      else {
        s += max(static_cast<K>(0), 1 + min(r, b) - max(l, a)) * node->value
        #ifdef TREE_MULTIPLY
          * multiplier
        #endif
        ;
        m = a + (b - a + 1) / 2 - 1;
        if (l <= m && a <= r && node->left) stack[++top] = {a, m, node->left
        #ifdef TREE_MULTIPLY
          , multiplier * node->multiplier
        #endif
        };
        if (l <= b && m <= r && node->right) stack[++top] = {m + 1, b, node->right
        #ifdef TREE_MULTIPLY
          , multiplier * node->multiplier
        #endif
        }; 
      }
    }
    return s;
  }
  #endif
  
  void add(const K l, const K r, V v) {
    static vector<tuple<K, K, Node*, char>> stack(128);
    int top = 0;
    stack[top] = {a, b, &root, 0};
    K a, b, m;
    Node* node;
    bool visited;
    while (top >= 0) {
      tie(a, b, node, visited) = stack[top];
      //err(a, b, node, top, l, r);
      if (visited) {
        --top;
        #ifdef TREE_MULTIPLY
          if (!(b < l || r < a) && !(l <= a && b <= r)) v *= node->multiplier;
        #endif
        //err("exiting", a, b, node->value);
        node->sum_ = node->value * (b - a + 1);
        if (node->left) node->sum_ += node->left->sum_
          #ifdef TREE_MULTIPLY
            * node->multiplier
          #endif
        ;
        if (node->right) node->sum_ += node->right->sum_
          #ifdef TREE_MULTIPLY
            * node->multiplier
          #endif
        ;
      } else {
        //err("entering", a, b);
        std::get<3>(stack[top]) = true;
        if (b < l || r < a);
        else if (l <= a && b <= r) { node->value += v; }
        else {
          #ifdef TREE_MULTIPLY
            v /= node->multiplier;
          #endif
          m = a + (b - a + 1) / 2 - 1;
          if (l <= m) {
            if (!node->left) node->left = new Node;
            stack[++top] = {a, m, node->left, false};
          }
          if (m < r) {
            if (!node->right) node->right = new Node;
            stack[++top] = {m + 1, b, node->right, false};
          }
        }
      }
    }
  }
  
  #ifdef TREE_MULTIPLY
  void multiply(const K l, const K r, const V v) {
    static vector<tuple<K, K, Node*, bool>> stack(128);
    int top = 0;
    stack[top] = {a, b, &root, false};
    K a, b, m;
    Node* node;
    bool visited;
    while (top >= 0) {
      tie(a, b, node, visited) = stack[top];
      //err(a, b, node, top, l, r);
      if (visited) {
        --top;
        //err("exiting", a, b, node->value);
        node->sum_ = node->value * (b - a + 1);
        if (node->left) node->sum_ += node->left->sum_
          #ifdef TREE_MULTIPLY
            * node->multiplier
          #endif
        ;
        if (node->right) node->sum_ += node->right->sum_
          #ifdef TREE_MULTIPLY
            * node->multiplier
          #endif
        ;
      } else {
        //err("entering", a, b);
        std::get<3>(stack[top]) = true;
        if (b < l || r < a);
        else if (l <= a && b <= r) {
          node->value *= v;
          node->multiplier *= v;
        }
        else {
          m = a + (b - a + 1) / 2 - 1;
          if (l <= m) {
            if (!node->left) node->left = new Node;
            stack[++top] = {a, m, node->left, false};
          }
          if (m < r) {
            if (!node->right) node->right = new Node;
            stack[++top] = {m + 1, b, node->right, false};
          }
        }
      }
    }
  }
  #endif
  
  friend ostream& operator << (ostream& o, const FastTree& t) {
    deque<string> lines = t.root.to_lines(t.a, t.b);
    size_t pad = 0;
    for (string_view l : lines) pad = max(pad, l.size());
    for (string& l : lines) l += string(pad - l.size(), ' ') + ']';
    for (string_view l : lines) o << l << endl;
    return o;
  }
};


struct Sum {};


template <typename V = long long>
struct Tree {
  const long long a, b;
  
  using Interval = pair<long long, long long>;
  
  inline static pair<Interval, Interval> split(const Interval& i) {
    auto [l, r] = i;
    long long m = l + (r - l + 1) / 2 - 1;
    return {{l, m}, {m + 1, r}};
  }
  
  inline static bool in(const Interval& i, const Interval& j) {
    return j.first <= i.first && i.second <= j.second;
  }
  
  inline static bool disjoint(const Interval& i, const Interval& j) {
    return i.second < j.first || j.second < i.first;
  }
  
  inline static bool intersect(const Interval& i, const Interval& j) {
    return !disjoint(i, j);
  }
  
  struct Node {
    #ifdef TREE_MULTIPLY
      V subtree_multiplier = 1;
    #endif
    V value = 0 /*,,  min_ = 0, max_ = 0 */;
    V sum_ = 0;
    Node *left = nullptr, *right = nullptr;
    
    ~Node() {
      if (left) delete left;
      if (right) delete right;
    }
    
    template <typename T>
    void set(const Interval& ni, long long l, const vector<T>& v) {
      Interval vi = {l, l + v.size() - 1};
      if (disjoint(ni, vi)) return;
      assert(value == 0);
      #ifdef TREE_MULTIPLY
        assert(subtree_multiplier == 1);
      #endif
      if (ni.first == ni.second) {
        value = v[ni.first - l];
      } else {
        auto [li, ri] = split(ni);
        if (intersect(li, vi)) {
          if (!left) left = new Node;
          left->set(li, l, v);
        }
        if (intersect(ri, vi)) {
          if (!right) right = new Node;
          right->set(ri, l, v);
        }
      }
      update(ni);
    }
    
    void set(const Interval& ni, const Interval& vi, V v) {
      if (disjoint(ni, vi)) return;
      if (in(ni, vi)) {
        value = v;
        #ifdef TREE_MULTIPLY
          subtree_multiplier = 1;
        #endif
        if (left) delete left; left = nullptr;
        if (right) delete right; right = nullptr;
      } else {
        v -= value;
        #ifdef TREE_MULTIPLY
          assert(subtree_multiplier != 0);
          v /= subtree_multiplier;
        #endif
        auto [li, ri] = split(ni);
        if (intersect(li, vi)) {
          if (!left) left = new Node;
          left->set(li, vi, v);
        }
        if (intersect(ri, vi)) {
          if (!right) right = new Node;
          right->set(ri, vi, v);
        }
      }
      update(ni);
    }
    
    
    void add(const Interval& ni, const Interval& vi, V v
      #ifdef TREE_MULTIPLY
        , V denominator
      #endif
    ) {
      if (disjoint(ni, vi)) return;
      if (in(ni, vi)) {
        value += v
          #ifdef TREE_MULTIPLY
            / denominator
          #endif
        ;
      } else {
        auto [li, ri] = split(ni);
        if (intersect(li, vi)) {
          if (!left) left = new Node;
          left->add(li, vi, v
            #ifdef TREE_MULTIPLY
              , denominator * subtree_multiplier
            #endif
          );
        }  
        if (intersect(ri, vi)) {
          if (!right) right = new Node;
          right->add(ri, vi, v
            #ifdef TREE_MULTIPLY
              , denominator * subtree_multiplier
            #endif
          );
        }
      }
      update(ni);
    }
    
    void multiply(const Interval& ni, const Interval& vi, V v) {
      if (disjoint(ni, vi)) return;
      if (v == 0) {
        set(ni, vi, 0);
      } else if (in(ni, vi)) {
        value *= v;
        subtree_multiplier *= v;
      } else {
        auto [li, ri] = split(ni);
        if (!left) left = new Node;
        if (!right) right = new Node;
        left->add(li, li, value, subtree_multiplier);
        right->add(ri, ri, value, subtree_multiplier);
        value = 0;
        left->multiply(li, vi, v);
        right->multiply(ri, vi, v);
      }
      update(ni);
    }
    
    void get(const Interval& ni, const Interval& qi, vector<V>& result,
        #ifdef TREE_MULTIPLY
          V multiplier = 1, 
        #endif
        V addition = 0) {
      if (disjoint(ni, qi)) return;
      V v  = 
      #ifdef TREE_MULTIPLY
        multiplier *
      #endif
        value + addition;
      if (ni.first == ni.second) {
        result.push_back(v);
      } else {
        const auto [li, ri] = split(ni);
        
        if (left) {
          left->get(li, qi, result, 
            #ifdef TREE_MULTIPLY
              multiplier * subtree_multiplier,
            #endif
            v);
        } else {
          for (long long i = std::max(li.first, qi.first);
              i <= std::min(li.second, qi.second); ++i)
            result.push_back(v);
        }
        
        if (right) {
          right->get(ri, qi, result,
            #ifdef TREE_MULTIPLY
              multiplier * subtree_multiplier,
            #endif
            v);
        } else {
          for (long long i = std::max(ri.first, qi.first);
               i <= std::min(ri.second, qi.second); ++i)
            result.push_back(v);
        }
      }
    }
    
    V sum(const Interval& ni, const Interval& qi, bool cache=true) {
      if (disjoint(ni, qi)) return 0;
      if (in(ni, qi) && cache) return sum_;
      auto [li, ri] = split(ni);
      return value * (std::min(ni.second, qi.second) - std::max(ni.first, qi.first) + 1)
        + 
        #ifdef TREE_MULTIPLY
          subtree_multiplier *
        #endif
        (
          (left ? left->sum(li, qi) : 0) +
          (right ? right->sum(ri, qi) : 0)); 
    }
    /*
    V min(const Interval& ni, const Interval& qi, bool cache=true) {
      assert(intersect(ni, qi));
      if (in(ni, qi) && cache) return min_;
    
      auto [li, ri] = split(ni);
      V kids = 0;
      if (intersect(li, qi) && intersect(ri, qi))
        kids = std::min(left ? left->min(li, qi) : 0, right ? right->min(ri, qi) : 0);
      else if (intersect(li, qi) && left)
        kids = left->min(li, qi);
      else if (intersect(ri, qi) && right)
        kids = right->min(ri, qi);
      return value + /*subtree_multiplier **/ /*kids;
    }*/
    
    // UNTESTED
    /*
    V max(const Interval& ni, const Interval& qi, bool cache=true) {
      assert(intersect(ni, qi));
      if (in(ni, qi) && cache) return max_;
    
      auto [li, ri] = split(ni);
      V kids = 0;
      if (intersect(li, qi) && intersect(ri, qi))
        kids = std::max(left ? left->max(li, qi) : 0, right ? right->max(ri, qi) : 0);
      else if (intersect(li, qi) && left)
        kids = left->max(li, qi);
      else if (intersect(ri, qi) && right)
        kids = right->max(ri, qi);
      return value + /*subtree_multiplier  *  kids;
    }*/
    
    void update(const Interval& i) {
      sum_ = sum(i, i, false);
      //max_ = max(i, i, false);
      //min_ = min(i, i, false);
    }
    /*
    void print() {
      if (left) left->print();
      if (value)
        //cout << "[" << a << ", " << b << "; len=" << b - a + 1 << "] " << value << " " << sum_ << endl; 
      if (right) right->print();
    }*/
  } root;
  
  Tree(long long a = -1e18, long long b = 1e18): a(a), b(b) {}
  
  void add(long long l, long long r, V v) {
    root.add({a, b}, {l, r}, v
      #ifdef TREE_MULTIPLY
        , 1
      #endif
    );
  }
  
  #ifdef TREE_MULTIPLY
  void multiply(long long l, long long r, V v) {
    root.multiply({a, b}, {l, r}, v);
  }
  #endif
  
  void set(long long l, long long r, V v) {
    root.set({a, b}, {l, r}, v);
  }
  
  template <typename T>
  void set(long long l, const vector<T>& v) {
    root.set({a, b}, l, v);
  }
  
  vector<V> get(long long l, long long r) {
    vector<V> result;
    result.reserve(r - l + 1);
    root.get({a, b}, {l, r}, result);
    return result;
  }
  
  V sum(long long l, long long r) {
    return root.sum({a, b}, {l, r});
  }
  
  
  /*
  V max(long long l, long long r) {
    return root.max({a, b}, {l, r});
  }
 
  V min(long long l, long long r) {
    return root.min({a, b}, {l, r});
  }*/
};

auto read_undirected(int n, int m) {
  vector e(n + 1, vector<int>());
  while (m--) {
    int u = _, v = _;
    e[u].push_back(v);
    e[v].push_back(u);
  }
  return e;
}

struct GraphSearchResult {
    GraphSearchResult(int size): d(size, -1), p(size), v_to_cc(size, -1) {};
  
    vector<int> postorder, d, p, v_to_cc;
    vector<vector<int>> cc;
};

GraphSearchResult dfs(const vector<vector<int>>& edges) {
  GraphSearchResult r(edges.size());
  auto& [postorder, d, p, v_to_cc, cc] = r;
  vector<pair<int, int>> q;
  for (int s = 1; s < edges.size(); ++s) if (d[s] < 0) {
    cc.push_back({});
    q.push_back({0, s});
    while (q.size()) {
      auto [w, u] = q.back();
      q.pop_back();
      if (d[u] >= 0) continue;
      postorder.push_back(u);
      d[u] = d[w] + 1;
      p[u] = w;
      v_to_cc[u] = cc.size() - 1;
      cc.back().push_back(u);
      for (int v : edges[u]) q.push_back({u, v});
    }
  } 
  std::reverse(postorder.begin(), postorder.end());
  return r;
}

vector<int> return_vertices(const vector<vector<int>>& edges, const GraphSearchResult& s) {
  vector<int> r(s.p.size(), -1);
  for (int u : s.postorder) {
    r[u] = u;
    int b = s.d[u];
    for (int v : edges[u]) if (v != s.p[u]) {
      int c = s.p[v] == u ? r[v] : v;
      if (s.d[c] < b) { b = s.d[c], r[u] = c; }
    }
  }
  return r;
}

struct GcdResult {
  long long g;
  long long x;
  long long y;
};

GcdResult extended_gcd(const long long aa, const long long bb) {
  assert(aa || bb);
  long long a = abs(aa), b = abs(bb);
  bool swapped = b > a;
  if (swapped) swap(a, b);
  static vector<long long> k(512);
  int i = 0;
  while (b) {
    k[i++] = a / b;
    a %= b;
    swap(a, b);
  }
  assert(i <= 512);
  long long x = 1, y = 0;
  while (i) {
    swap(x, y);
    y -= x * k[--i];
  }
  if (swapped) swap(x, y);
  return {a, aa < 0 ? -x : x, bb < 0 ? -y : y};
}

long long inv(long long a, long long m) {
  GcdResult r = extended_gcd(a, m);
  assert(r.g == 1);
  long long result = (r.x % m + m) % m;
  assert(0 <= result);
  assert(result < m);
  return result;
}

long long lcm(long long a, long long b) {
  return (a / std::gcd(a, b)) * b;
}

inline long long power(long long a, long long b, long long m) {
  long long r = 1;
  for (long long i = 0, e = (a % m); (1 << i) <= b; ++i, e = (e * e) % m)
    if (b & (1 << i)) r = (r * e) % m;
  return r;
}

struct Operators {
  /*
  inline friend auto operator -= (auto& f, const auto& g) {
    return f += -g;
  }
  
  inline friend auto operator /= (auto& f, const auto& g) {
    return f *= g.inv();
  }
  */
  
};

struct Fraction : Operators {

  inline friend Fraction operator -= (Fraction& f, const Fraction& g) {
    return f += -g;
  }
  
  inline friend Fraction operator /= (Fraction& f, const Fraction& g) {
    return f *= g.inv();
  }

  friend Fraction operator + (Fraction f, const Fraction& g) {
    return f += g;
  }
  
  friend Fraction operator - (Fraction f, const Fraction& g) {
    return f -= g;
  } 
  
  friend Fraction operator * (Fraction f, const Fraction& g) {
    return f *= g;
  }

  friend Fraction operator / (Fraction f, const Fraction& g) {
    return f /= g;
  }
  
  friend bool operator == (const Fraction& f, const Fraction& g) {
    long long l = lcm(f.denominator, g.denominator);
    return f.numerator * (l / f.denominator) == g.numerator * (l / g.denominator);
  }
  
  friend bool operator < (const Fraction& f, const Fraction& g) {
    long long l = lcm(f.denominator, g.denominator);
    return f.numerator * (l / f.denominator) < g.numerator * (l / g.denominator);
  }

  long long numerator = 0, denominator = 1;
  
  Fraction() {}
  Fraction(long long n) : numerator(n) {}
  Fraction(long long n, long long d) : numerator(n), denominator(d) {
    simplify();
  }
  
  Fraction operator += (const Fraction& f) {
    long long l = lcm(denominator, f.denominator);
    numerator = numerator * (l / denominator) + f.numerator * (l / f.denominator);
    denominator = l;
    simplify();
    return *this;
  }
  
  Fraction operator - () const {
    return {-numerator, denominator};
  }
  
  Fraction operator *= (const Fraction& f) {
    long long g1 = __gcd(numerator, f.denominator),
      n1 = numerator / g1,
      d1 = f.denominator / g1,
      g2 = __gcd(denominator, f.numerator),
      n2 = f.numerator / g2,
      d2 = denominator / g2;
    numerator = n1 * n2;
    denominator = d1 * d2;
    simplify();
    return *this;
  }

  Fraction inv() const {
    return {denominator, numerator};
  }
  
  void simplify() {
    long long g = __gcd(numerator, denominator);
    numerator /= g;
    denominator /= g;
    if (denominator < 0) {
      numerator = -numerator;
      denominator = -denominator;
    }
  }
  
  friend ostream& operator << (ostream& o, const Fraction& f) {
    o << f.numerator << "/" << f.denominator ;
    return o;
  }
};

template <long long M=998244353>
struct Mod {
  
  inline Mod<M> operator -= (Mod<M> g) {
    return value = (value + M - g.value) % M;
  }
  
  inline Mod<M> operator /= (Mod<M> g) {
    return  value = (value * ::inv(g.value, M)) % M;
  }
  
  inline friend Mod<M> operator + (Mod<M> f, Mod<M> g) {
    return f += g;
  }
  
  inline friend Mod<M> operator - (Mod<M> f, Mod<M> g) {
    return f -= g;
  } 
  
  inline friend Mod<M> operator * (Mod<M> f, Mod<M> g) {
    return f *= g;
  }

  inline friend Mod<M> operator / (Mod<M> f, Mod<M> g) {
    return f /= g;
  }
  
  inline friend bool operator == (Mod<M> f, Mod<M> g) {
    return f.value == g.value;
  }
  
  inline friend bool operator < (Mod<M> f, Mod<M> g) {
    return f.value < g.value;
  }

  long long value;
  
  inline Mod(long long v = 0) : value((M + v % M) % M) {}
  
  inline Mod<M> operator += (Mod<M> b) {
    value = (value + b.value) % M;
    return *this;
  }
  
  inline Mod<M> operator - () const {
    return M - value;
  }
  
  inline Mod<M> operator *= (Mod<M> b) {
    value = (value * b.value) % M;
    return *this;
  }

  inline Mod<M> inv() const {
    return ::inv(value, M);
  }
  
  inline friend ostream& operator << (ostream& o, Mod<M> a) {
    o << a.value;
    return o;
  }
};

map<long long, long long> factorize(long long n) {
  map<long long, long long> r;
  for (long long i = 2; i * i <= n; ++i)
    for (; n % i == 0; n /= i)
      ++r[i];
  if (n > 1) ++r[n];
  return r;
}

template<typename T, typename U>
auto cdiv(T t, U u) {
  return (t + u - 1) / u;
}

inline vector<int> subsets(int s) {
  vector<int> change;
  for (int t = s, b = 1 << __builtin_ctz(t) ; t; t ^= b, b = 1 << __builtin_ctz(t))
      change.push_back(b - (s & (b - 1)));
  vector<int> r = {0};
  int over = 1 << __builtin_popcount(s);
  for (int t = 1, st = 0; t < over; ++t) 
    r.push_back(st += change[__builtin_ctz(t)]);
  return r;
}

const vector<pair<int, int>> four_directions {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};

template <typename V>
bool is_index(const vector<V>& v, int i, int j) {
  return 0 <= i && i < v.size() && 0 <= j && j < v[i].size();
}

template <typename V>
bool is_index(const vector<V>& v, pair<int, int> ij) {
  return is_index(v, ij.first, ij.second);
}

auto indices(const vector<string>& v) {
  vector<pair<int, int>> r;
  for (int i = 0; i < v.size(); ++i)
    for (int j = 0; j < v[i].size(); ++j)
      r.push_back({i, j});
  return r;
}

auto four_neighbors(const vector<string>& b, pair<int, int> i) {
  vector<pair<int, int>> r;
  for (auto d : four_directions)
    if (is_index(b, i + d))
      r.push_back(i + d);
  return r;
}

vector<string> get_rotated_clockwise(const vector<string>& t) {
  vector<string> r(t[0].size(), string(t.size(), ' '));
  for (int i = 0; i < t.size(); ++i)
    for (int j = 0; j < t[0].size(); ++j)
      r[j][t.size() - i - 1] = t[i][j];
  return r;
}

template <typename T>
long long sum(const T& t) {
  return std::accumulate(begin(t), end(t), 0ll);
}

vector<long long> get_partial_sums(const vector<long long>& v) {
  vector<long long> p {0};
  partial_sum(v.cbegin(), v.cend(), back_inserter(p));
  return p;
}

void Yes(bool b) {
  out(b ? "Yes" : "No");
}

// Wczytać wektor i inne kolekcje stringów

void testTreeParity() {
  {
    const long long M = 2000000000;
    Tree t(-M, M);
    FastTree<long long> f{-M, M};
    for (long long i = 0; ; ++i) {
      if (i % 100000 == 0) out(i);
      {
        long long a = rand() % M, b = rand() % M, v = rand() % M;
        if (a > b) swap(a, b);
        err("add", a, b, v);
        t.add(a, b, v);
        f.add(a, b, v);
      }
      {
        //cerr << f;
        long long k = rand() % M;
        long long tr = t.get(k, k)[0], fr = f[k];
        err("get", k, tr, fr); 
        assert(tr == fr);
      }
      #ifdef TREE_SUM
      {
        long long a = rand() % M, b = rand() % M;
        if (a > b) swap(a, b);
        long long tr = t.sum(a, b), fr = f.sum(a, b);
        if (tr != fr) {
          cerr << f;
          out("sum", a, b, tr, fr);
        }
        assert(tr == fr);
      }
      #endif
      #ifdef TREE_MULTIPLY
      {
        long long a = rand() % M, b = rand() % M, v = rand() % M;
        if (a > b) swap(a, b);
        err("multiply", a, b, v);
        t.multiply(a, b, v);
        f.multiply(a, b, v);
      }
      #endif
    }
  }
}

void testTreeSpeed() {
  {
    const int M = 2000000000;
    //Tree<long long> t;
    FastTree<long long> t;
    for (long long i = 0; i < 500000; ++i) {
      if (i % 100000 == 0) err(i);
      {
        long long a = rand() % M, b = rand() % M, v = rand() % M;
        if (a > b) swap(a, b);
        //err("add", a, b, v);
        t.add(a, b, v);
      }
      {
        //cerr << f;
        //long long k = rand() % M;
        //long long tr = t.sum(k, k);//t.get(k, k)[0];
        //long long fr = t[k];
      }
      {
        long long a = rand() % M, b = rand() % M;
        if (a > b) swap(a, b);
        t.sum(a, b);
      }
    }
  }
}

int main() {
  std::ios::sync_with_stdio(false);
  cout << setprecision(50);
  cerr << setprecision(50);
  /*
  for (long long m = 7; m < 100; ++m)
    for (long long n = 1; n < 100; ++n) {
      err(m, n);
      assert(E((n * (n + 1) / 2) % m) == E(((n % m) * ((n + 1) % m) / 2) % m));
    }*/
  
  int tests = _;
  while (tests--) {
    string s = _;
    long long m = _, n = 0;
    for (char c : s) n = (n * 10 + c - '0') % m;
    out(m % 2 == 0 && n == m - 1 ? m / 2 : (n * (n + 1) / 2) % m);
  }
  
  return 0;
}