#include <bits/stdc++.h>
using namespace std;
#define FASTIO ios::sync_with_stdio(false); cin.tie(0); cout.tie(0)
#define MULTIPLE_TEST int t; cin>>t; while(t--)
#define bit(x,i) (x&(1<<i))
#define lowbit(x) ((x)&((x)^((x)-1)))
#define hBit(msb,n) asm("bsrl %1,%0" : "=r"(msb) : "r"(n))
#define FOR(i,L,R) for (int i = L; i < R; i++)
#define FER(i,L,R) for (int i = L; i <= R; i++)
#define FOD(i,L,R) for (int i = L; i > R; i--)
#define FED(i,L,R) for (int i = L; i >= R; i--)
#define clr(a,x) memset(a,x,sizeof(a))
#define all(c) (c).begin(),(c).end()
#define PRESENT(c,x) ((c).find(x) != (c).end())
#define CPRESENT(c,x) (find(ALL(c),x) != (c).end())
#define MAX(a, b) a = max(a, b)
#define MIN(a, b) a = min(a, b)
#define INF 0x7fffffff
#define ll long long
#define mp make_pair
#define fi first
#define se second
#define pb push_back
#define eb emplace_back
#define gcd
#define MAXN 10005
#define MOD 1000000007
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef pair<string, string> pss;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<pii> vii;
typedef vector<ll> vl;
typedef vector<vl> vvl;