/* 29 . 03 . 2008 */
#include <bits/stdc++.h>
using namespace std ;
bool watbor = 1;
typedef long long ll ;
typedef vector<int> vi ;
typedef vector<pair<int,int>> vii ;
typedef pair<int,int> pii ;
typedef pair<ll,int> pli ;
typedef pair<int,ll> pil ;
typedef pair<ll,ll> pll ;
#define FOR(i,a,b) for(int i(a) ; i <= (int)b ; i++)
#define FORD(i,a,b) for(int i(a) ; i >= (int)b ; i--)
#define FORN(i,a,b) for(int i(a) ; i < (int)b ; i++)
#define all(a) a.begin() , a.end()
#define pb push_back
#define fi first
#define se second
#define endl '\n'
#define BIT(mask,i) ((mask>>(i))&1)
#define builtin_popcount builtin_popcountll
#define uni(a) sort(all(a)), a.resize(unique(all(a))-a.begin())
#define MASK(a) (1ll << a)
int gcd(int x, int y) {return __gcd(x, y) ;}
int lg(int x) {return __lg(x) ;}
int lcm(int x, int y) {return x / __gcd(x, y) * y ;}
template <class T> bool maxi(T &x,T y) { if (x < y) { x = y ; return true ;} return false ;}
template <class T> bool mini(T &x,T y) { if (x > y) { x = y ; return true ;} return false ;}
const int N = 2e5 + 5, M = 5e3 + 5, LG = __lg(N) + 1, base = 311 ;
const int oo = 2e9, sm = 1e9 + 7, mod1 = 1e9 + 7, mod2 = 998244353 ;
const long long inf = 1e18 ;
void init(){
}
void solve(){
}
signed main(){
ios_base::sync_with_stdio(0) ; cin.tie(0) ; cout.tie(0) ;
#define task ""
if(fopen(task".inp","r")){
freopen(task".inp","r",stdin) ;
freopen(task".out","w",stdout) ;
}
int tc ; tc = 1 ;
if(watbor) cin >> tc ;
FOR(bqc, 1, tc) {
init() ;
solve() ;
}
cerr << "\nTime : " << clock() * 0.001 << "s" << endl ;
return 0 ;
}
/* Watbor */
LyogMjkgLiAwMyAuIDIwMDggKi8gCiNpbmNsdWRlIDxiaXRzL3N0ZGMrKy5oPgp1c2luZyBuYW1lc3BhY2Ugc3RkIDsKCmJvb2wgd2F0Ym9yID0gMTsKCnR5cGVkZWYgbG9uZyBsb25nIGxsIDsKdHlwZWRlZiB2ZWN0b3I8aW50PiB2aSA7CnR5cGVkZWYgdmVjdG9yPHBhaXI8aW50LGludD4+IHZpaSA7CnR5cGVkZWYgcGFpcjxpbnQsaW50PiBwaWkgOwp0eXBlZGVmIHBhaXI8bGwsaW50PiBwbGkgOwp0eXBlZGVmIHBhaXI8aW50LGxsPiBwaWwgOwp0eXBlZGVmIHBhaXI8bGwsbGw+IHBsbCA7CgojZGVmaW5lIEZPUihpLGEsYikgZm9yKGludCBpKGEpIDsgaSA8PSAoaW50KWIgOyBpKyspCiNkZWZpbmUgRk9SRChpLGEsYikgZm9yKGludCBpKGEpIDsgaSA+PSAoaW50KWIgOyBpLS0pCiNkZWZpbmUgRk9STihpLGEsYikgZm9yKGludCBpKGEpIDsgaSA8IChpbnQpYiA7IGkrKykKI2RlZmluZSBhbGwoYSkgYS5iZWdpbigpICwgYS5lbmQoKQojZGVmaW5lIHBiIHB1c2hfYmFjawojZGVmaW5lIGZpIGZpcnN0CiNkZWZpbmUgc2Ugc2Vjb25kCiNkZWZpbmUgZW5kbCAnXG4nIAojZGVmaW5lIEJJVChtYXNrLGkpICgobWFzaz4+KGkpKSYxKQojZGVmaW5lIGJ1aWx0aW5fcG9wY291bnQgYnVpbHRpbl9wb3Bjb3VudGxsCiNkZWZpbmUgdW5pKGEpIHNvcnQoYWxsKGEpKSwgYS5yZXNpemUodW5pcXVlKGFsbChhKSktYS5iZWdpbigpKSAKI2RlZmluZSBNQVNLKGEpICgxbGwgPDwgYSkgCgppbnQgZ2NkKGludCB4LCBpbnQgeSkge3JldHVybiBfX2djZCh4LCB5KSA7fQppbnQgbGcoaW50IHgpIHtyZXR1cm4gX19sZyh4KSA7fQppbnQgbGNtKGludCB4LCBpbnQgeSkge3JldHVybiB4IC8gX19nY2QoeCwgeSkgKiB5IDt9Cgp0ZW1wbGF0ZSA8Y2xhc3MgVD4gYm9vbCBtYXhpKFQgJngsVCB5KSB7IGlmICh4IDwgeSkgeyB4ID0geSA7IHJldHVybiB0cnVlIDt9IHJldHVybiBmYWxzZSA7fQp0ZW1wbGF0ZSA8Y2xhc3MgVD4gYm9vbCBtaW5pKFQgJngsVCB5KSB7IGlmICh4ID4geSkgeyB4ID0geSA7IHJldHVybiB0cnVlIDt9IHJldHVybiBmYWxzZSA7fQoKY29uc3QgaW50IE4gPSAyZTUgKyA1LCBNID0gNWUzICsgNSwgTEcgPSBfX2xnKE4pICsgMSwgYmFzZSA9IDMxMSA7CmNvbnN0IGludCBvbyA9IDJlOSwgc20gPSAxZTkgKyA3LCBtb2QxID0gMWU5ICsgNywgbW9kMiA9IDk5ODI0NDM1MyA7CmNvbnN0IGxvbmcgbG9uZyBpbmYgPSAxZTE4IDsKCgp2b2lkIGluaXQoKXsKCgp9CgoKCnZvaWQgc29sdmUoKXsKCgp9CgpzaWduZWQgbWFpbigpewogICAgaW9zX2Jhc2U6OnN5bmNfd2l0aF9zdGRpbygwKSA7IGNpbi50aWUoMCkgOyBjb3V0LnRpZSgwKSA7IAoKICAgICNkZWZpbmUgdGFzayAiIgogICAgaWYoZm9wZW4odGFzayIuaW5wIiwiciIpKXsKICAgICAgICBmcmVvcGVuKHRhc2siLmlucCIsInIiLHN0ZGluKSA7IAogICAgICAgIGZyZW9wZW4odGFzayIub3V0IiwidyIsc3Rkb3V0KSA7IAogICAgfQoKICAgIGludCB0YyA7IHRjID0gMSA7CiAgICBpZih3YXRib3IpIGNpbiA+PiB0YyA7CgogICAgRk9SKGJxYywgMSwgdGMpIHsKICAgICAgICBpbml0KCkgOwogICAgICAgIHNvbHZlKCkgOwogICAgfQoKICAgIGNlcnIgPDwgIlxuVGltZSA6ICIgPDwgY2xvY2soKSAqIDAuMDAxIDw8ICJzIiA8PCBlbmRsIDsKICAgIHJldHVybiAwIDsgCn0KLyogV2F0Ym9yICov