Polycarp has recently created a new level in this cool new game Berlio Maker 85 and uploaded it online. Now players from all over the world can try his level.

All levels in this game have two stats to them: the number of plays and the number of clears. So when a player attempts the level, the number of plays increases by 1. If he manages to finish the level successfully then the number of clears increases by 1 as well. Note that both of the statistics update at the same time (so if the player finishes the level successfully then the number of plays will increase at the same time as the number of clears).

Polycarp is very excited about his level, so he keeps peeking at the stats to know how hard his level turns out to be.

So he peeked at the stats n times and wrote down n pairs of integers — (p_1, c_1), (p_2, c_2), ..., (p_n, c_n), where p_i is the number of plays at the i-th moment of time and c_i is the number of clears at the same moment of time. The stats are given in chronological order (i.e. the order of given pairs is exactly the same as Polycarp has written down).

Between two consecutive moments of time Polycarp peeked at the stats many players (but possibly zero) could attempt the level.

Finally, Polycarp wonders if he hasn't messed up any records and all the pairs are correct. If there could exist such a sequence of plays (and clears, respectively) that the stats were exactly as Polycarp has written down, then he considers his records correct.

Help him to check the correctness of his records.

For your convenience you have to answer multiple independent test cases.

Input

The first line contains a single integer T (1 ≤ T ≤ 500) — the number of test cases.

The first line of each test case contains a single integer n (1 ≤ n ≤ 100) — the number of moments of time Polycarp peeked at the stats.

Each of the next n lines contains two integers p_i and c_i (0 ≤ p_i, c_i ≤ 1000) — the number of plays and the number of clears of the level at the i-th moment of time.

Note that the stats are given in chronological order.

Output

For each test case print a single line.

If there could exist such a sequence of plays (and clears, respectively) that the stats were exactly as Polycarp has written down, then print "YES".

Otherwise, print "NO".

You can print each letter in any case (upper or lower).

Example

Input


6
3
0 0
1 1
1 2
2
1 0
1000 3
4
10 1
15 2
10 2
15 2
1
765 432
2
4 4
4 3
5
0 0
1 0
1 0
1 0
1 0


Output


NO
YES
NO
YES
NO
YES

Note

In the first test case at the third moment of time the number of clears increased but the number of plays did not, that couldn't have happened.

The second test case is a nice example of a Super Expert level.

In the third test case the number of plays decreased, which is impossible.

The fourth test case is probably an auto level with a single jump over the spike.

In the fifth test case the number of clears decreased, which is also impossible.

Nobody wanted to play the sixth test case; Polycarp's mom attempted it to make him feel better, however, she couldn't clear it.
1
2
110 2
115 112
 10
5
88 60
10 3
48 21
90 70
40 88
5
20 81
39 98
34 87
100 82
21 21
2
46 91
89 71
2
81 98
25 36
3
84 97
40 32
17 29
2
56 16
96 75
5
35 24
82 73
23 15
45 95
79 90
2
68 13
70 100
3
94 35
95 77
31 86
5
99 14
12 54
81 60
80 29
46 55
 4
1
1 2
3
1 1
2 2
3 2
3
1 1
1 1
1 1
5
0 0
0 0
1 0
1 0
2 2
 1
2
100 1
101 3
 1
3
5 4
8 8
9 8
 1
2
4 1
5 3
 1
2
3 1
4 3
 1
2
10 2
12 5
 1
2
5 0
6 3
 1
3
2 2
10 3
11 5
 1
2
500 0
501 400
 1
2
2 0
7 6
 1
5
5 1
6 3
7 4
8 5
9 5
 1
2
5 3
10 9
 1
4
4 2
7 6
8 8
9 9
 19
1
1 1
1
2 2
1
3 3
1
4 4
1
5 5
1
6 6
1
7 7
1
8 8
1
9 9
1
10 10
1
11 11
1
12 12
1
13 13
1
14 14
1
15 15
1
16 16
1
17 17
1
18 18
1
19 19
 1
2
5 1
7 4
 1
3
1 1
2 1
3 3
 1
2
10 1
11 4
 1
2
2 0
3 2
 2
3
4 2
5 5
6 6
3
1 1
3 3
4 4
 1
2
6 3
7 5
 1
2
4 3
8 8
 1
2
10 8
20 19
 1
2
10 1
11 7
 1
2
5 2
6 5
 1
5
1 1
2 1
3 1
4 1
5 3
 1
2
3 2
5 5
 1
3
1 0
4 0
6 4
 1
3
0 0
2 1
3 3
 1
2
4 3
6 6
 1
3
0 0
10 1
15 7
 3
3
2 1
3 2
4 4
2
5 3
5 6
2
2 2
3 2
 1
3
10 2
12 7
13 8
 1
3
5 2
6 5
7 6
 1
3
10 9
11 11
11 11
 1
3
1 1
10 1
11 7
 1
2
5 1
6 3
 1
3
5 0
7 4
10 10
 20
2
1 0
1000 3
3
4 2
4 2
4 2
3
0 0
1 1
1 2
2
1 0
1000 3
4
10 1
15 2
10 2
15 2
1
765 432
2
4 4
4 3
5
0 0
1 0
1 0
1 0
1 0
3
0 0
1 1
1 2
2
1 0
1000 3
4
10 1
15 2
10 2
15 2
1
765 432
2
4 4
4 3
5
0 0
1 0
1 0
1 0
1 0
3
0 0
1 1
1 2
2
1 0
1000 3
4
10 1
15 2
10 2
15 2
1
765 432
2
4 4
4 3
5
0 0
1 0
1 0
1 0
1 0
 1
3
99 49
100 50
101 99
 2
4
1 1
10 10
100 10
1000 920
4
1 5
1000 100
1000 100
1000 100
 11
5
85 49
90 49
92 50
95 50
99 50
5
85 49
90 49
92 50
95 50
99 50
1
3 4
5
42 18
70 25
82 28
96 43
99 48
5
37 50
95 50
100 50
100 50
100 50
5
59 34
100 38
100 38
100 39
100 41
5
40 39
97 47
97 50
99 50
100 50
5
42 18
70 25
82 28
96 43
99 48
5
37 50
95 50
100 50
100 50
100 50
5
59 34
100 38
100 38
100 39
100 41
5
40 39
97 47
97 50
99 50
100 50
 1
2
10 3
13 8
 1
3
1 1
2 1
5 5
 1
2
1 0
10 10
 1
3
1 1
5 1
6 6
 1
3
1 1
3 2
4 4
 1
3
0 0
100 0
101 2
 1
2
5 3
6 5
 1
2
765 432
767 436
 1
2
10 0
11 2
 1
2
10 1
12 7
 1
3
1 1
3 2
7 7
 10
2
1 2
3 3
1
5 3
2
3 0
4 5
1
3 5
1
0 5
2
5 4
0 4
2
0 1
0 5
1
4 3
2
5 3
2 5
2
5 4
5 1
 1
3
7 3
8 4
9 6
 2
2
1 0
2 2
1
0 1
 1
4
1 0
3 2
13 13
15 15
 1
2
4 3
7 7
 1
3
1 1
10 3
13 7
 1
3
401 1
402 2
403 4
 1
2
5 1
6 6
 1
2
4 3
5 5
 2
3
0 0
100 0
104 5
3
0 0
100 0
104 4
 1
2
10 2
11 4
 1
3
0 0
11 5
21 20
 1
2
12 10
15 15
 1
2
3 2
4 4
 1
3
1 1
30 10
31 20
 1
3
0 0
5 1
7 4
 1
2
10 8
12 11
 1
2
11 0
13 4
 1
2
10 5
11 7
 1
2
5 2
6 4
 1
2
5 2
7 6
 1
2
2 1
5 5
 1
2
6 2
8 5
 1
2
5 0
7 3
 1
3
0 0
50 20
55 30
 1
3
5 2
6 4
7 6
 1
3
1 1
30 20
40 40
 1
4
0 0
1 0
2 0
3 3
 1
2
1 0
3 3
 1
3
3 2
4 2
5 5
 1
2
18 10
22 15
 1
2
1 0
2 2
 1
2
4 1
10 9
 1
2
100 51
101 99
 1
2
10 8
11 10
 1
3
0 0
4 3
5 5
 1
2
100 10
101 101
 1
2
43 34
44 35
 1
2
10 5
16 12
 1
2
10 1
101 101
 1
2
4 3
9 9
 1
2
10 7
12 10
 1
3
1 1
10 1
11 5
 1
2
4 2
5 4
 1
3
1 0
5 1
6 3
 1
4
1 1
2 1
5 1
6 3
 1
4
1 0
2 1
4 4
6 5
 1
2
100 50
101 99
 1
2
7 6
8 8
 1
2
100 3
105 50
 1
2
5 0
10 6
 1
2
5 4
6 6
 1
2
4 2
6 5
 1
4
0 0
1 1
10 1
11 3
 1
3
1 1
500 1
501 99
 1
5
1 0
1 0
5 1
6 3
7 4
 2
2
2 0
3 2
3
0 0
3 1
4 3
 1
2
30 10
31 21
 1
4
1 0
5 4
10 5
11 7
 1
4
3 2
5 4
8 8
9 9
 1
2
10 1
11 10
 1
3
0 0
10 5
11 8
 1
3
1 1
100 1
101 10
 1
3
4 2
5 4
6 5
 1
2
11 1
12 3
 1
11
1 1
1 1
3 1
20 18
21 19
43 41
43 41
44 42
46 44
47 45
48 47
 1
2
8 1
9 5
 1
2
5 2
9 8
 1
5
25 10
26 12
27 13
28 14
29 15
 1
2
2 1
3 3
 1
2
5 0
7 4
 1
2
13 10
16 15
 1
2
10 3
11 5
 1
5
1 0
1 0
5 5
6 6
7 7
 1
2
5 1
6 4
 1
2
6 1
8 4
 1
2
5 2
15 14
 1
3
0 0
5 3
6 6
 1
3
0 0
3 1
4 3
 1
2
3 1
5 4
 1
2
2 1
4 4
 1
2
3 0
5 5
 1
99
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
 3
2
1 0
4 4
1
1 2
2
4 0
6 3
 1
4
4 1
5 1
6 4
6 4
 4
3
2 1
3 2
4 4
2
5 3
5 6
2
2 2
3 2
3
1 1
2 2
145 1
 5
5
42 18
70 25
82 28
96 43
99 48
5
85 49
90 49
92 50
95 50
99 50
5
37 50
95 50
100 50
100 50
100 50
5
59 34
100 38
100 38
100 39
100 41
5
40 39
97 47
97 50
99 50
100 50
 1
2
3 1
6 6
 1
2
5 1
8 5
 1
2
108 1
110 22
 1
2
10 1
11 3
 1
3
5 1
6 3
7 4
 2
2
4 1
5 3
2
100 50
101 99
 1
3
1 1
4 1
5 3
 1
3
1 1
4 2
5 4
 1
4
0 0
0 0
2 1
3 3
 1
3
2 1
4 1
5 3
 1
2
3 0
5 3
 1
3
10 5
12 8
13 9
 1
3
5 0
7 5
8 8
 1
2
5 2
8 6
 1
3
0 0
5 3
6 5
 1
3
4 2
6 5
6 5
 1
2
10 6
15 12
 1
2
10 1
12 4
 1
2
100 5
101 10
 1
2
100 3
105 9
 1
2
2 0
3 3
 1
2
100 0
101 2

NO
 NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
 NO
YES
YES
NO
 NO
 NO
 NO
 NO
 NO
 NO
 NO
 NO
 NO
 NO
 NO
 NO
 YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
 NO
 NO
 NO
 NO
 NO
YES
 NO
 NO
 NO
 NO
 NO
 NO
 NO
 NO
 NO
 NO
 NO
 NO
NO
YES
 NO
 NO
 NO
 NO
 NO
 NO
 YES
YES
NO
YES
NO
YES
NO
YES
NO
YES
NO
YES
NO
YES
NO
YES
NO
YES
NO
YES
 NO
 NO
NO
 YES
YES
NO
NO
NO
NO
NO
NO
NO
NO
NO
 NO
 NO
 NO
 NO
 NO
 NO
 NO
 NO
 NO
 NO
 NO
 NO
YES
NO
NO
NO
NO
NO
YES
NO
NO
 NO
 NO
NO
 NO
 NO
 NO
 NO
 NO
 NO
 NO
YES
 NO
 NO
 NO
 NO
 NO
 NO
 NO
 NO
 NO
 NO
 NO
 NO
 NO
 NO
 NO
 NO
 NO
 NO
 NO
 NO
 NO
 NO
 NO
 NO
 NO
 NO
 NO
 YES
 NO
 NO
 NO
 NO
 NO
 NO
 NO
 NO
 NO
 NO
 NO
 NO
 NO
 NO
 NO
 NO
 NO
 NO
 NO
NO
 NO
 NO
 NO
 NO
 NO
 NO
 NO
 NO
 NO
 NO
 NO
 NO
 NO
 NO
 NO
 NO
 NO
 NO
 NO
 NO
 NO
 NO
 NO
 NO
 NO
 YES
 NO
NO
NO
 NO
 NO
NO
YES
NO
 NO
YES
NO
NO
NO
 NO
 NO
 NO
 NO
 NO
 NO
NO
 NO
 NO
 NO
 NO
 NO
 NO
 NO
 NO
 NO
 NO
 NO
 NO
 NO
 NO
 NO
 NO

##############--->>>>> Deepcoder Amit Kumar Bhuyan <<<<<---##############

"""
 Perfection is achieved not when there is nothing more to add, but rather when there is nothing more to take away.
"""
from __future__ import division, print_function
 
import os,sys
from io import BytesIO, IOBase
 
if sys.version_info[0] < 3:
    from __builtin__ import xrange as range
    from future_builtins import ascii, filter, hex, map, oct, zip
 
 
def ii():  return int(input())
def si():  return input()
def mi():  return map(int,input().strip().split(" "))
def msi(): return map(str,input().strip().split(" "))
def li():  return list(mi())
 
def dmain():
    sys.setrecursionlimit(1000000)
    threading.stack_size(1024000)
    thread = threading.Thread(target=main)
    thread.start()
    
#from collections import deque, Counter, OrderedDict,defaultdict
#from heapq import nsmallest, nlargest, heapify,heappop ,heappush, heapreplace
#from math import log,sqrt,factorial,cos,tan,sin,radians
#from bisect import bisect,bisect_left,bisect_right,insort,insort_left,insort_right
#from decimal import *
#import threading
#from itertools import permutations
#Copy 2D list  m = [x[:] for x in mark] .. Avoid Using Deepcopy
import sys
input = sys.stdin.readline
scanner = lambda: int(input())
string = lambda: input().rstrip()
get_list = lambda: list(read())
read = lambda: map(int, input().split())
get_float = lambda: map(float, input().split())
# from bisect import bisect_left as lower_bound;
# from bisect import bisect_right as upper_bound;
# from math import ceil, factorial;

 
def ceil(x):
    if x != int(x):
        x = int(x) + 1
    return x
 
def factorial(x, m):
	val = 1
	while x>0:
		val = (val * x) % m
		x -= 1
	return val

def fact(x):
	val = 1
	while x > 0:
		val *= x
		x -= 1
	return val
    
# swap_array function
def swaparr(arr, a,b):
    temp = arr[a];
    arr[a] = arr[b];
    arr[b] = temp;
 
## gcd function
def gcd(a,b):
    if b == 0:
        return a;
    return gcd(b, a % b);

## lcm function
def lcm(a, b):
	return (a * b) // math.gcd(a, b)

def is_integer(n):
	return math.ceil(n) == math.floor(n)
 
## nCr function efficient using Binomial Cofficient
def nCr(n, k): 
	if k > n:
		return 0
	if(k > n - k):
		k = n - k
	res = 1
	for i in range(k):
		res = res * (n - i)
		res = res / (i + 1)
	return int(res)
 
## upper bound function code -- such that e in a[:i] e < x;

 
## prime factorization
def primefs(n):
    ## if n == 1    ## calculating primes
    primes = {}
    while(n%2 == 0 and n > 0):
        primes[2] = primes.get(2, 0) + 1
        n = n//2
    for i in range(3, int(n**0.5)+2, 2):
        while(n%i == 0 and n > 0):
            primes[i] = primes.get(i, 0) + 1
            n = n//i
    if n > 2:
        primes[n] = primes.get(n, 0) + 1
    ## prime factoriazation of n is stored in dictionary
    ## primes and can be accesed. O(sqrt n)
    return primes
 
## MODULAR EXPONENTIATION FUNCTION
def power(x, y, p): 
    res = 1
    x = x % p  
    if (x == 0) : 
        return 0
    while (y > 0) : 
        if ((y & 1) == 1) : 
            res = (res * x) % p 
        y = y >> 1      
        x = (x * x) % p 
    return res 
 
## DISJOINT SET UNINON FUNCTIONS
def swap(a,b):
    temp = a
    a = b
    b = temp
    return a,b;
 
# find function with path compression included (recursive)
# def find(x, link):
#     if link[x] == x:
#         return x
#     link[x] = find(link[x], link);
#     return link[x];
 
# find function with path compression (ITERATIVE)
def find(x, link):
    p = x;
    while( p != link[p]):
        p = link[p];
    
    while( x != p):
        nex = link[x];
        link[x] = p;
        x = nex;
    return p;
 
 
# the union function which makes union(x,y)
# of two nodes x and y
def union(x, y, link, size):
    x = find(x, link)
    y = find(y, link)
    if size[x] < size[y]:
        x,y = swap(x,y)
    if x != y:
        size[x] += size[y]
        link[y] = x
 
## returns an array of boolean if primes or not USING SIEVE OF ERATOSTHANES
def sieve(n): 
    prime = [True for i in range(n+1)] 
    prime[0], prime[1] = False, False
    p = 2
    while (p * p <= n): 
        if (prime[p] == True): 
            for i in range(p * p, n+1, p):
                prime[i] = False
        p += 1
    return prime

# Euler's Toitent Function phi
def phi(n) : 
  
    result = n 
    p = 2
    while(p * p<= n) : 
        if (n % p == 0) : 
            while (n % p == 0) : 
                n = n // p 
            result = result * (1.0 - (1.0 / (float) (p))) 
        p = p + 1
    if (n > 1) : 
        result = result * (1.0 - (1.0 / (float)(n))) 
   
    return (int)(result) 

def is_prime(n):
	if n == 0:
		return False
	if n == 1:
		return True
	for i in range(2, int(n ** (1 / 2)) + 1):
		if not n % i:
			return False
 
	return True

def next_prime(n, primes):
	while primes[n] != True:
		n += 1
	return n

 
#### PRIME FACTORIZATION IN O(log n) using Sieve ####
MAXN = int(1e5 + 5)
def spf_sieve():
    spf[1] = 1;
    for i in range(2, MAXN):
        spf[i] = i;
    for i in range(4, MAXN, 2):
        spf[i] = 2;
    for i in range(3, ceil(MAXN ** 0.5), 2):
        if spf[i] == i:
            for j in range(i*i, MAXN, i):
                if spf[j] == j:
                    spf[j] = i;
    ## function for storing smallest prime factors (spf) in the array
 
################## un-comment below 2 lines when using factorization #################
spf = [0 for i in range(MAXN)]
# spf_sieve();
def factoriazation(x):
    res = []
    for i in range(2, int(x ** 0.5) + 1):
    	while x % i == 0:
    		res.append(i)
    		x //= i
    if x != 1:
   		res.append(x)
    return res
    ## this function is useful for multiple queries only, o/w use
    ## primefs function above. complexity O(log n)

def factors(n):
	res = []
	for i in range(1, int(n ** 0.5) + 1):
		if n % i == 0:
			res.append(i)
			res.append(n // i)
	return list(set(res))
 
## taking integer array input
def int_array():
    return list(map(int, input().strip().split()));
 
def float_array():
    return list(map(float, input().strip().split()));
 
## taking string array input
def str_array():
    return input().strip().split();

def binary_search(low, high, w, h, n):
	while low < high:
		mid = low + (high - low) // 2
		# print(low, mid, high)
		if check(mid, w, h, n):
			low = mid + 1
		else:
			high = mid
	return low

## for checking any conditions
def check(moves, n):
	val = (moves + 1) // 2
	rem = moves - val
	sol = (val + 1) * (rem + 1)
	return sol < n
	

## for sorting according to second position
def sortSecond(val):
	return val[1]
	

 
#defining a couple constants
MOD = int(1e9)+7;
CMOD = 998244353;
INF = float('inf'); NINF = -float('inf');
alphs = "abcdefghijklmnopqrstuvwxyz"
 
################### ---------------- TEMPLATE ENDS HERE ---------------- ###################
 
from itertools import permutations
import math
import bisect as bis
import random
import sys
import collections as collect
import functools as fnt
from decimal import Decimal
# from sys import stdout
# import numpy as np
"""
_______________
rough work here
_______________



"""

def solve():
    n = scanner()
    pc = []
    for i in range(n):
        pc.append(get_list())
    if pc[0][0] < pc[0][1]:
        print("NO")
        return
    for i in range(1, n):
        if pc[i][0] == pc[i - 1][0]:
            if pc[i][0] < pc[i][1]:
                print("NO")
                return
            elif pc[i][1] < pc[i - 1][1]:
                print("NO")
                return
            elif pc[i][1] - pc[i - 1][1] > pc[i][0] - pc[i - 1][0]:
                print("NO")
                return
        elif pc[i][0] < pc[i - 1][0]:
            print("NO")
            return
        elif pc[i][0] > pc[i - 1][0]:
            if pc[i][0] < pc[i][1]:
                print("NO")
                return
            elif pc[i][1] < pc[i - 1][1]:
                print("NO")
                return
            elif pc[i][1] - pc[i - 1][1] > pc[i][0] - pc[i - 1][0]:
                print("NO")
                return
    print("YES")



# region fastio
# template taken from https://github.com/cheran-senthil/PyRival/blob/master/templates/template.py
 
BUFSIZE = 8192
 
 
class FastIO(IOBase):
    newlines = 0
 
    def __init__(self, file):
        self._fd = file.fileno()
        self.buffer = BytesIO()
        self.writable = "x" in file.mode or "r" not in file.mode
        self.write = self.buffer.write if self.writable else None
 
    def read(self):
        while True:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            if not b:
                break
            ptr = self.buffer.tell()
            self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
        self.newlines = 0
        return self.buffer.read()
 
    def readline(self):
        while self.newlines == 0:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            self.newlines = b.count(b"\n") + (not b)
            ptr = self.buffer.tell()
            self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
        self.newlines -= 1
        return self.buffer.readline()
 
    def flush(self):
        if self.writable:
            os.write(self._fd, self.buffer.getvalue())
            self.buffer.truncate(0), self.buffer.seek(0)
 
 
class IOWrapper(IOBase):
    def __init__(self, file):
        self.buffer = FastIO(file)
        self.flush = self.buffer.flush
        self.writable = self.buffer.writable
        self.write = lambda s: self.buffer.write(s.encode("ascii"))
        self.read = lambda: self.buffer.read().decode("ascii")
        self.readline = lambda: self.buffer.readline().decode("ascii")
 
 
def print(*args, **kwargs):
    """Prints the values to a stream, or to sys.stdout by default."""
    sep, file = kwargs.pop("sep", " "), kwargs.pop("file", sys.stdout)
    at_start = True
    for x in args:
        if not at_start:
            file.write(sep)
        file.write(str(x))
        at_start = False
    file.write(kwargs.pop("end", "\n"))
    if kwargs.pop("flush", False):
        file.flush()
 
 
if sys.version_info[0] < 3:
    sys.stdin, sys.stdout = FastIO(sys.stdin), FastIO(sys.stdout)
else:
    sys.stdin, sys.stdout = IOWrapper(sys.stdin), IOWrapper(sys.stdout)
 
input = lambda: sys.stdin.readline().rstrip("\r\n")
 
# endregion
 
 
if __name__ == "__main__":
    #read()
    # sys.stdin = open("input.txt", "r")
    # sys.stdout = open("output.txt", "w")
    t = scanner()
    for i in range(t):
    	solve()
    #dmain()
 
# Comment Read()
	# fin_time = datetime.now()
# 	print("Execution time (for loop): ", (fin_time-init_time))
