description: Theofanis has a riddle for you and if you manage to solve it, he will give you a Cypriot snack halloumi for free (Cypriot cheese).
  
  You are given an integer n. You need to find two integers l and r such that -10^{18} ≤ l < r ≤ 10^{18} and l + (l + 1) + … + (r - 1) + r = n.
  
  Input
  
  The first line contains a single integer t (1 ≤ t ≤ 10^4) — the number of test cases.
  
  The first and only line of each test case contains a single integer n (1 ≤ n ≤ 10^{18}).
  
  Output
  
  For each test case, print the two integers l and r such that -10^{18} ≤ l < r ≤ 10^{18} and l + (l + 1) + … + (r - 1) + r = n. 
  
  It can be proven that an answer always exists. If there are multiple answers, print any.
  
  Example
  
  Input
  
  
  7
  1
  2
  3
  6
  100
  25
  3000000000000
  
  
  Output
  
  
  0 1
  -1 2 
  1 2 
  1 3 
  18 22
  -2 7
  999999999999 1000000000001
  
  Note
  
  In the first test case, 0 + 1 = 1.
  
  In the second test case, (-1) + 0 + 1 + 2 = 2.
  
  In the fourth test case, 1 + 2 + 3 = 6.
  
  In the fifth test case, 18 + 19 + 20 + 21 + 22 = 100.
  
  In the sixth test case, (-2) + (-1) + 0 + 1 + 2 + 3 + 4 + 5 + 6 + 7 = 25.
solution: import java.awt.Container;
  import java.awt.image.SampleModel;
  import java.io.BufferedReader;
  import java.io.FileInputStream;
  import java.io.FileNotFoundException;
  import java.io.IOException;
  import java.io.InputStreamReader;
  import java.util.*;
  import java.util.concurrent.CountDownLatch;
  
  import javax.naming.TimeLimitExceededException;
  
  import java.io.PrintStream;
  
  
  public class Solution {
  
  	static class Pair<T,V>{
  		T first;
  		V second;
  		public Pair(T first, V second) {
  			super();
  			this.first = first;
  			this.second = second;
  		}
  		
  
  	}
  
  	// public static final boolean LOCAL = System.getProperty("ONLINE_JUDGE")==null;
  	private static FastScanner fs=new FastScanner();
  	private static Scanner sc=new Scanner(System.in);
  
  	private static int uperBound(long[] arr, long val) {
  
  		int start= 0; 
  		int end=arr.length;
  		while(start<end) {
  			int mid=(start+end)/2;
  			if( arr[mid]==val ) {
  				return mid;
  			}
  			if( arr[mid]>val ) {
  				end=mid-1;
  			}else {
  				start=mid+1;
  			}
  		}
  
  		if( start >= arr.length || arr[start]>val) {
  			return start;
  		}else {
  			return start+1;
  		}
  
  	}
  
  
  	
  	private static void solve(int TC) throws Exception{
  		/*WRITE CODE HERE*/
  
  		
  		long n=fs.nextLong();
  		
  		
  		System.out.println((-(n-1))+" "+n);
  		
  		
  		
  		/*int n=fs.nextInt();
  		
  		int arr[]=new int[n+1];
  		
  		for(int i=2;i<=n;i++) {
  			//System.out.println("#1");
  			if( arr[i]==0 ) {
  				for(int j=2*i;j<=n;j+=i) {
  					arr[j]++;
  					//System.out.println("#2");
  				}
  			}
  		}
  		int count=0;
  		for(int i=2;i<=n;i++) {
  			//System.out.println("#3");
  			if(arr[i]==2) {
  				count++;
  			}
  		}
  		
  		System.out.println(count);
  		
  		/*int n = fs.nextInt(), x = fs.nextInt();
          int[] a =new int[n];
          for(int i=0;i<n;i++) {
          	a[i]=fs.nextInt();
          }
          int[] b = a.clone();
          Arrays.sort(b);
          for (int i = 0; i < n; i++) {
              if (i < x && n - 1 - i < x && a[i] != b[i]) {
                  System.out.println("NO");
                  return;
              }
          }
          System.out.println("YES");
  		
  		/*int n=fs.nextInt();
  		int x=fs.nextInt();
  		ArrayList<Long> list=new ArrayList<Long>();
  		for(int i=0;i<n;i++) {
  			list.add(fs.nextLong());
  		}
  		
  		ArrayList<Long> copy=(ArrayList<Long>)list.clone();
  		
  		Collections.sort(copy);
  		
  		for(int i=0;i<n;i++) {
  			if( copy.get(i)!=list.get(i) ) {
  				if( i < x && n - 1 - i < x ) {
  					System.out.println("NO");
  					return;
  				}
  			}
  		}
  		System.out.println("YES");
  				
  		/*int n=fs.nextInt();
  		int h=fs.nextInt();
  		ArrayList<Integer> list=new ArrayList<Integer>();
  		for(int i=0;i<n;i++) {
  			list.add(fs.nextInt());
  		}
  		Collections.sort(list, Collections.reverseOrder());
  		int sum=list.get(0)+list.get(1);
  		int count= (h/sum)*2 ;
  		int left=h%sum;
  		if( left<=list.get(0) && left!=0 ) {
  			count++;
  		}else if(left!=0){
  			count+=2;
  		}
  		
  		System.out.println(count);
  		
  		
  		
  		
  		
  		/*int n=fs.nextInt();
  		
  		PriorityQueue<Pair<Integer,Integer>> pq=new PriorityQueue<Solution.Pair<Integer,Integer>>( (o1,o2)-> o2.first.compareTo(o1.first) );
  		
  		
  		for(int i=1;i<=n;i++) {
  			int num=fs.nextInt();
  			if(num==0) {
  				continue;
  			}
  			pq.add(new Pair<Integer,Integer>(num, i));
  		}
  		
  		ArrayList<Pair<Integer,Integer>> ans=new ArrayList<Solution.Pair<Integer,Integer>>();
  		
  		while(pq.size()>1) {
  			Pair p1=pq.poll();
  			Pair p2=pq.poll();
  			
  			ans.add(new Pair(p1.second, p2.second));
  			p1.first=(int)p1.first-1;
  			p2.first=(int)p2.first-1;
  			
  			if(!p1.first.equals(0)) pq.add(p1);
  			if(!p2.first.equals(0)) pq.add(p2);
  		}
  		
  		System.out.println(ans.size());
  		for(Pair p:ans) {
  			System.out.println(p.first+" "+p.second);
  		}
  		
  		
  		/*int r=fs.nextInt();
  		int col=fs.nextInt();
  		int k=fs.nextInt();
  		
  		char arr[][]=new char[r][col];
  		
  		for(int i=0;i<r;i++) {
  			char  ch[]=fs.next().toCharArray();
  			arr[i]=ch;
  		}
  		
  		boolean visited[][]=new boolean[r][col];
  		for(boolean b[]:visited) {
  			Arrays.fill(b, false);
  		}
  		
  		for(int i=r-1;i>=1;i--) {
  			for(int j=1;j<col-1;j++) {
  				if( arr[i][j]=='*' ) {
  					
  					int len = 0;
  	                int a1 = i - 1, l1 = j - 1, l2 = j + 1;
  	                ArrayList<Pair<Integer, Integer>> v=new ArrayList<Solution.Pair<Integer,Integer>>();
  	                while (a1 >= 0 && l1 >= 0 && l2 < col) {
  	                    if (arr[a1][l1] == '*' && arr[a1][l2] == '*') {
  	                        len++;
  	                        v.add(new Pair(a1,l1));
  	                        v.add(new Pair(a1,l2));
  	                        l1--;
  	                        l2++;
  	                        a1--;
  	                        continue;
  	                    }
  	                    break;
  	                }
  	                if (len < k && visited[i][j] == false) {
  	                    System.out.println("NO");
  	                    return;
  	                }
  	                if (len >= k) {
  	                    for (Pair p:v) {
  	                        visited[(int)p.first][(int)p.second] = true;
  	                    }
  	                }
  	                visited[i][j] = true;
  					
  					
  					
  				}
  			}
  			
  		}
  		
  		for (int i = 0; i < r; i++) {
  	        for (int j = 0; j < col; j++) {
  	            if (arr[i][j] == '*' && !visited[i][j]) {
  	                System.out.println("NO");
  	                return;
  	            }
  	        }
  	    }
  		
  		System.out.println("YES");
  		
  		
  		/*int n=fs.nextInt();
  		int arr[]=new int[n+1];
  		for(int i=1;i<=n;i++) {
  			arr[i]=fs.nextInt();
  		}
  		ArrayList<int[]> list=new ArrayList<int[]>();
  		int smallAns[]=new int[3];
  		for(int i=1;i<=n ;i++) {
  			int minI=i;
  			for(int j=i+1;j<=n;j++) {
  				if(arr[minI]>arr[j]) {
  					minI=j;
  				}
  			}
  			
  			if(minI==i) {
  				continue;
  			}
  			//System.out.println(minI);
  			int temp=arr[minI];
  			for(int j=minI;j>i;j--) {
  				arr[j]=arr[j-1];
  			}
  			arr[i]=temp;
  			smallAns[0]=i;
  			smallAns[1]=minI;
  			smallAns[2]=minI-i;
  			list.add(Arrays.copyOf(smallAns,smallAns.length));
  		}
  		
  		System.out.println(list.size());
  		for(int i=0;i<list.size();i++) {
  			System.out.println(list.get(i)[0]+" "+list.get(i)[1]+" "+list.get(i)[2]);
  		}
  		/*System.out.println("sort");
  		for(int i=1;i<=n;i++) {
  			System.out.print(arr[i]+" ");
  		}
  		System.out.println();
  		
  		/*String s=fs.next();
  		int a=0;
  		int b=0;
  		int c=0;
  		for(int i=0;i<s.length();i++) {
  			if(s.charAt(i)=='A') {
  				a++;
  			}else if( s.charAt(i)=='B' ) {
  				b++;
  			}else {
  				c++;
  			}
  		}
  		
  		if( a+c==b ) {
  			System.out.println("YES");
  		}else {
  			System.out.println("NO");
  		}
  		
  		/*int w=fs.nextInt();
  		int h=fs.nextInt();
  		
  		int x1=fs.nextInt();
  		int y1=fs.nextInt();
  		int x2=fs.nextInt();
  		int y2=fs.nextInt();
  		
  		int tw=fs.nextInt();
  		int th=fs.nextInt();
  		
  		if( !( ( w>= (Math.abs(x1-x2)+tw) || h>= (Math.abs(y1-y2)+th) ) || ( w>= ( Math.abs(x1-x2)+th ) || h>= ( Math.abs(y1-y2)+tw ) ) ) ) {
  			System.out.println(-1);
  			return ;
  		}
  		int ans=Integer.MAX_VALUE;
  		if( y1>= th || h-y2>=th ) {
  			ans=0;
  		}else if( th+y2-y1 <= h ) {
  			ans= th-y1;
  			
  			ans = Math.min(ans, th-( h-y2 ) );
  		}
  		
  		if( x1>=tw || w-x2 >= tw) {
  			ans=0;
  		}else if( tw+ x2-x1 <= w ) {
  			ans=Math.min(ans, tw-x1 );
  			
  			ans= Math.min(ans, tw-(w-x2) );
  		}
  		
  		if(ans== Integer.MAX_VALUE ) {
  			System.out.println(-1);
  		}else if( ans<0 ) {
  			System.out.println(0);
  		}else
  			System.out.println(ans);
  		
  		
  		/*int col=fs.nextInt();
  		
  		int in[][]=new int[2][col];
  		for(int i=0;i<col;i++) {
  			in[0][i]=fs.nextInt();
  		}
  		for(int i=0;i<col;i++) {
  			in[1][i]=fs.nextInt();
  		}
  		
  		int leftSum[][]=new int[2][col];
  		leftSum[0][0]=in[0][0];
  		leftSum[1][0]=in[1][0];
  		
  		for(int i=1;i<col;i++) {
  			leftSum[0][i]=in[0][i]+leftSum[0][i-1];
  			leftSum[1][i]=in[1][i]+leftSum[1][i-1];
  		}
  		
  
  		int rightSum[][]=new int[2][col];
  		rightSum[0][col-1]=in[0][col-1];
  		rightSum[1][col-1]=in[1][col-1];
  		
  		for(int i=col-2;i>=0;i--) {
  			rightSum[0][i]=rightSum[0][i+1] + in[0][i];
  			rightSum[1][i]=rightSum[1][i+1] + in[1][i];
  		}
  		
  		
  		int minScore=Integer.MAX_VALUE;
  		for(int i=0;i<col;i++) {
  			int score1= ( i+1<col ) ? rightSum[0][i+1] : 0;
  			int score2= (i-1>=0) ? leftSum[1][i-1] : 0;
  			minScore= Math.min(minScore, Math.max(score1, score2));
  		}
  		
  		System.out.println(minScore);
  		
  		/*int n=fs.nextInt();
  		long input[]=new long[n];
  		for(int i=0;i<n;i++) {
  			input[i]=fs.nextLong();
  		}
  
  
  		int even=0;
  		for(int i=0;i<n;i++) {
  			if( (input[i]&1) ==0 ) {
  				even++;
  			}
  		}
  		int odd=n-even;
  		if( Math.abs(odd-even) > 1 ) {
  			System.out.println(-1);
  			return ;
  		}
  		
  		for(int i=0;i<n;i++) {
  			input[i]= ( (input[i]&1)==1 )?1 :0;
  		}
  		
  		int ans=Integer.MAX_VALUE;
  		if( (n&1)==0 ) {
  			int output[]=new int[n];
  			for(int i=0;i<n;i++) {
  				output[i] = ( i&1 )==1 ? 1:0;
  			}
  			
  			ArrayList<Integer> oddpos=new ArrayList<Integer>();
  			ArrayList<Integer> evenpos=new ArrayList<Integer>();
  			
  			for(int i=0;i<n;i++) {
  				if( input[i] != output[i] ) {
  					if( (i&1)==1 ) oddpos.add(i); 
  					else evenpos.add(i);
  				}
  			}
  			int smallAns=0;
  			for(int i=0;i<oddpos.size();i++) {
  				smallAns+= Math.abs(oddpos.get(i)-evenpos.get(i));
  			}
  			
  			ans=Math.min(ans, smallAns);
  			
  			output=new int[n];
  			for(int i=0;i<n;i++) {
  				output[i] = ( i&1 )==0 ? 1:0;
  			}
  			
  			oddpos=new ArrayList<Integer>();
  			evenpos=new ArrayList<Integer>();
  			
  			for(int i=0;i<n;i++) {
  				if( input[i] != output[i] ) {
  					if( (i&1)==1 ) oddpos.add(i); 
  					else evenpos.add(i);
  				}
  			}
  			smallAns=0;
  			for(int i=0;i<oddpos.size();i++) {
  				smallAns+= Math.abs(oddpos.get(i)-evenpos.get(i));
  			}
  			
  			ans=Math.min(ans, smallAns);
  		}else if( odd> even ) {
  			int output[]=new int[n];
  			for(int i=0;i<n;i++) {
  				output[i] = ( i&1 )==0 ? 1:0;
  			}
  			
  			ArrayList<Integer> oddpos=new ArrayList<Integer>();
  			ArrayList<Integer> evenpos=new ArrayList<Integer>();
  			
  			for(int i=0;i<n;i++) {
  				if( input[i] != output[i] ) {
  					if( (i&1)==1 ) oddpos.add(i); 
  					else evenpos.add(i);
  				}
  			}
  			int smallAns=0;
  			for(int i=0;i<oddpos.size();i++) {
  				smallAns+= Math.abs(oddpos.get(i)-evenpos.get(i));
  			}
  			
  			ans=Math.min(ans, smallAns);
  		}else {
  			int output[]=new int[n];
  			for(int i=0;i<n;i++) {
  				output[i] = ( i&1 )==1 ? 1:0;
  			}
  			
  			ArrayList<Integer> oddpos=new ArrayList<Integer>();
  			ArrayList<Integer> evenpos=new ArrayList<Integer>();
  			
  			for(int i=0;i<n;i++) {
  				if( input[i] != output[i] ) {
  					if( (i&1)==1 ) oddpos.add(i); 
  					else evenpos.add(i);
  				}
  			}
  			int smallAns=0;
  			for(int i=0;i<oddpos.size();i++) {
  				smallAns+= Math.abs(oddpos.get(i)-evenpos.get(i));
  			}
  			
  			ans=Math.min(ans, smallAns);
  		}
  		
  		
  		System.out.println(ans);
  
  		/*
  		int len=fs.nextInt();
  		String row1=fs.next();
  		String row2=fs.next();
  
  		int prev=-1;
  		int count=0;
  
  		for(int i=0;i<len; i++) {
  			if( row1.charAt(i) != row2.charAt(i) ) {
  				count+=2;
  				prev=-1;
  			}else if ( row1.charAt(i)=='1') {
  				if(prev==0) {
  					count++;
  					prev=-1;
  				}else {
  					prev=1;
  				}
  			}else {
  				if(prev==1) {
  					count+=2;
  					prev=-1;
  				}else {
  					count++;
  					prev=0;
  				}
  			}
  		}
  
  		System.out.println(count);
  
  		/*int a=fs.nextInt();
  		int b=fs.nextInt();
  		int c=fs.nextInt();
  		int m=fs.nextInt();
  
  		int max=a+b+c-3;
  
  		int arr[]= {a,b,c};
  		Arrays.parallelSort(arr);
  
  		int min=arr[2]-arr[1]-arr[0]-1;
  		if(m>=min && m<=max) {
  			System.out.println("YES");
  		}else {
  			System.out.println("No");
  		}
  		 */
  		/*
  		int n=fs.nextInt();
  		long hero[]=new long[n];
  		long sum=0;
  		for(int i=0;i<n;i++) {
  			hero[i]=Long.parseLong(fs.next());
  			sum+=hero[i];
  		}
  		//System.out.println(sum);
  		Arrays.sort(hero);
  		//for(long x: hero)
  			//System.out.print(x+" ");
  		//System.out.println();
  		int m=fs.nextInt();
  		while(m-->0) {
  
  			long df=Long.parseLong(fs.next());
  			long at=Long.parseLong(fs.next());
  
  
  
  			long nextGrt=(long)Math.pow(10, 18);
  			long nextSmall=-1;
  			int index=uperBound(hero, df);
  			//System.out.println(hero[index]);
  			//System.out.println(index);
  			if(index>=n) {
  				nextSmall=hero[n-1];
  			}else if(index<=0 ) {
  				nextGrt=hero[0];
  			}else {
  				nextGrt=hero[index];
  				nextSmall=hero[index-1];
  			}
  
  			/*for(int i=0;i<n;i++) {
  				if(hero[i]>=df &&  hero[i]<nextGrt  ) {
  					nextGrt=hero[i];
  				}
  				if(hero[i]<=df && hero[i]>nextSmall ) {
  					nextSmall=hero[i];
  				}
  			}
  
  			//System.out.println(nextGrt +" : "+nextSmall);
  
  			if( nextGrt!= (long) Math.pow(10, 18) && sum-nextGrt >=at ) {
  				System.out.println(0);
  			}else {
  				if(nextGrt==(long)Math.pow(10, 18)) {
  
  					long ans= df- nextSmall;
  					ans+= ( at<= ( sum-nextSmall ) ) ? 0 : (at- sum+nextSmall);
  					System.out.println(ans);
  				}
  				else if(nextSmall==-1) {
  					long ans= ( at <= sum- nextGrt ) ? 0 : ( at- sum+nextGrt);
  					System.out.println(ans);
  				}else {
  					long ans1=df- nextSmall;
  					ans1+= ( at<= ( sum-nextSmall ) ) ? 0 : (at- sum+nextSmall);
  
  					long ans2= ( at <= sum- nextGrt ) ? 0 : ( at- sum+nextGrt);
  
  					System.out.println(Math.min(ans1, ans2));
  				}
  			}
  
  
  
  		}
  
  
  		/*int n=fs.nextInt();
  
  		for(int i=1;i<=n;i++) {
  			String open="";
  			String close="";
  			for(int j=1;j<=i;j++) {
  				open+="(";
  				close+=")";
  			}
  
  			int j=0;
  			while( j+2*i <= 2* n) {
  				System.out.print(open);
  				System.out.print(close);
  				j=j+2*i;
  			}
  			//System.out.println(j);
  			if(j<2*n) {
  				while(j<2*n) {
  					System.out.print("(");
  					System.out.print(")");
  					j+=2;
  				}
  			}
  			System.out.println();
  		}
  
  		 */
  
  	}
  
  	public static void main(String[] args) throws Exception {
  
  		int tcr=1; 
  		//tcr = sc.nextInt();
  		tcr=fs.nextInt();
  
  		while(tcr-->0) {
  			solve(tcr);
  
  		}
  
  		System.gc();
  
  	}
  
  
  	static int computeXOR(int n)
  	{
  		// If n is a multiple of 4
  		if (n % 4 == 0)
  			return n;
  
  		// If n%4 gives remainder 1
  		if (n % 4 == 1)
  			return 1;
  
  		// If n%4 gives remainder 2
  		if (n % 4 == 2)
  			return n + 1;
  
  		// If n%4 gives remainder 3
  		return 0;
  	}
  
  	static boolean isSorted (int[] nums) {
  
  		for (int i = 0; i < nums.length - 1; i++) {
  
  			if (nums[i] > nums[i + 1]) {
  
  				return false;
  
  			}
  
  		}
  
  		return true;
  
  	}
  
  	static void firstOperation (int[] nums) {
  
  		for (int i = 1; i < nums.length; i += 2) {
  
  			int temp = nums[i];
  			nums[i] = nums[i - 1];
  			nums[i - 1] = temp;
  
  		}
  
  	}
  
  	static void secondOperation (int[] nums) {
  
  		int n = nums.length / 2;
  
  		for (int i = 0; i < n; i++) {
  
  			int temp = nums[i];
  			nums[i] = nums[i + n];
  			nums[i + n] = temp;
  
  		}
  
  	}
  
  
  	private static long numOfDigits(long a) {
  		long ans=0;
  		while(a!=0) {
  			ans++;
  			a/=10;
  		}
  		return ans;
  	}
  
  	private static String reverse(String s) {
  		String ans="";
  		for(int i=s.length()-1;i>=0;i--) {
  			ans+=s.charAt(i);
  		}
  		return ans;
  	}
  
  	private static boolean isPalindrome(String s) {
  		int i=0;
  		int j=s.length()-1;
  
  		while(i<j) {
  			if(s.charAt(i)!=s.charAt(j)) {
  				return false;
  			}
  			i++;
  			j--;
  		}
  		return true;
  	}
  
  	static class FastScanner {
  
  		BufferedReader br;
  		StringTokenizer st ;
  
  		FastScanner(){
  			br =  new BufferedReader(new InputStreamReader(System.in));
  			st = new StringTokenizer("");
  		}
  
  		FastScanner(String file) {
  
  			try {
  				br =  new BufferedReader(new InputStreamReader(new FileInputStream(file)));
  				st = new StringTokenizer("");
  			} catch (FileNotFoundException e) {
  				// TODO Auto-generated catch block
  				System.out.println("file not found");
  				e.printStackTrace();
  			}
  
  		}
  
  
  		String next() {
  			while (!st.hasMoreTokens())
  				try {
  					st = new StringTokenizer(br.readLine());
  				} catch (IOException e) {
  				}
  			return st.nextToken();
  		}
  
  		int nextInt() {
  			return Integer.parseInt(next());
  		}
  
  		long nextLong() {
  			return Long.parseLong(next());
  		}
  		String readLine() throws IOException{
  			return br.readLine();
  		}
  	}
  
  	public static long[] sort(long arr[]){
  		List<Long> list = new ArrayList<>();
  		for(long n : arr){list.add(n);}
  		Collections.sort(list);
  		for(int i=0;i<arr.length;i++){
  			arr[i] = list.get(i);
  		}
  		return arr;
  	}
  	public static int[] sort(int arr[]){
  		List<Integer> list = new ArrayList<>();
  		for(int n : arr){list.add(n);}
  		Collections.sort(list);
  		for(int i=0;i<arr.length;i++){
  			arr[i] = list.get(i);
  		}
  		return arr;
  	}
  
  	// return the (index + 1)
  	// where index is the pos of just smaller element
  	// i.e count of elemets strictly less than num
  	public static int justSmaller(long arr[],long num){
  		//  System.out.println(num+"@");
  		int st = 0;
  		int e = arr.length - 1;
  
  		int ans = -1;
  
  		while(st <= e){
  
  			int mid = (st + e)/2;
  
  			if(arr[mid] >= num){
  				e = mid - 1;
  			}else{
  				ans = mid;
  				st = mid + 1;
  			}
  
  		}
  
  
  		return ans + 1;
  
  	}
  
  	//return (index of just greater element)
  	//count of elements smaller than or equal to num
  
  	public static int justGreater(long arr[],long num){
  		int st = 0;
  		int e = arr.length - 1;
  
  		int ans = arr.length;
  
  		while(st <= e){
  
  			int mid = (st + e)/2;
  
  			if(arr[mid] <= num){
  				st = mid + 1;
  			}else{
  				ans = mid;
  				e = mid - 1;
  			}
  		}
  
  		return ans;
  
  	}
  
  
  	public static boolean isPrime(int n) {
  
  		for(int i=2;i<n;i++) {
  			if(n%i==0) {
  				return false;
  			}
  		}
  		return true;
  	}
  
  	public static void println(Object obj){
  		System.out.println(obj.toString());
  	}
  
  	public static void print(Object obj){
  		System.out.println(obj.toString());
  	}
  
  	public static long gcd(long a,long b){
  		if(b == 0l){
  			return a;
  		}
  
  		return gcd(b,a%b);
  	}
  
  	public static int find(int parent[],int v){
  		if(parent[v] == v){
  			return v;
  		}
  
  		return parent[v] = find(parent, parent[v]);
  	}
  
  
  
  	public static List<Integer> sieve(){
  
  		List<Integer> prime = new ArrayList<>();
  
  		int arr[] = new int[100001];
  
  		Arrays.fill(arr,1);
  
  		arr[1] = 0;
  		arr[2] = 1;
  
  		for(int i=2;i<=100000;i++){
  
  			if(arr[i] == 1){
  
  				prime.add(i);
  
  				for(long j = (i*1l*i);j<100001;j+=i){
  					arr[(int)j] = 0;
  				}
  			}
  		}
  
  		return prime;
  	}
  
  	static boolean isPower(long n,long a){
  
  		long log = (long)(Math.log(n)/Math.log(a));
  
  		long power = (long)Math.pow(a,log);
  
  		if(power == n){return true;}
  
  		return false;
  	}
  
  
  	private static int mergeAndCount(int[] arr, int l,int m, int r)
  	{
  
  		// Left subarray
  		int[] left =  Arrays.copyOfRange(arr, l, m + 1);
  
  		// Right subarray
  		int[] right = Arrays.copyOfRange(arr, m + 1, r + 1);
  
  		int i = 0, j = 0, k = l, swaps = 0;
  
  		while (i < left.length && j < right.length) {
  			if (left[i] <= right[j])
  				arr[k++] = left[i++];
  			else {
  				arr[k++] = right[j++];
  				swaps += (m + 1) - (l + i);
  			}
  		}
  		while (i < left.length)
  			arr[k++] = left[i++];
  		while (j < right.length)
  			arr[k++] = right[j++];
  		return swaps;
  	}
  
  	// Merge sort function
  	private static int mergeSortAndCount(int[] arr, int l,int r)
  	{
  
  		// Keeps track of the inversion count at a
  		// particular node of the recursion tree
  		int count = 0;
  
  		if (l < r) {
  			int m = (l + r) / 2;
  
  			// Total inversion count = left subarray count
  			// + right subarray count + merge count
  
  			// Left subarray count
  			count += mergeSortAndCount(arr, l, m);
  
  			// Right subarray count
  			count += mergeSortAndCount(arr, m + 1, r);
  
  			// Merge count
  			count += mergeAndCount(arr, l, m, r);
  		}
  
  		return count;
  	}
  
  	static class Debug {
  		//change to System.getProperty("ONLINE_JUDGE")==null; for CodeForces
  		public static final boolean LOCAL = System.getProperty("ONLINE_JUDGE")==null;
  		private static <T> String ts(T t) {
  			if(t==null) {
  				return "null";
  			}
  			try {
  				return ts((Iterable) t);
  			}catch(ClassCastException e) {
  				if(t instanceof int[]) {
  					String s = Arrays.toString((int[]) t);
  					return "{"+s.substring(1, s.length()-1)+"}\n";
  				}else if(t instanceof long[]) {
  					String s = Arrays.toString((long[]) t);
  					return "{"+s.substring(1, s.length()-1)+"}\n";
  				}else if(t instanceof char[]) {
  					String s = Arrays.toString((char[]) t);
  					return "{"+s.substring(1, s.length()-1)+"}\n";
  				}else if(t instanceof double[]) {
  					String s = Arrays.toString((double[]) t);
  					return "{"+s.substring(1, s.length()-1)+"}\n";
  				}else if(t instanceof boolean[]) {
  					String s = Arrays.toString((boolean[]) t);
  					return "{"+s.substring(1, s.length()-1)+"}\n";
  				}
  				try {
  					return ts((Object[]) t);
  				}catch(ClassCastException e1) {
  					return t.toString();
  				}
  			}
  		}
  		private static <T> String ts(T[] arr) {
  			StringBuilder ret = new StringBuilder();
  			ret.append("{");
  			boolean first = true;
  			for(T t: arr) {
  				if(!first) {
  					ret.append(", ");
  				}
  				first = false;
  				ret.append(ts(t));
  			}
  			ret.append("}");
  			return ret.toString();
  		}
  		private static <T> String ts(Iterable<T> iter) {
  			StringBuilder ret = new StringBuilder();
  			ret.append("{");
  			boolean first = true;
  			for(T t: iter) {
  				if(!first) {
  					ret.append(", ");
  				}
  				first = false;
  				ret.append(ts(t));
  			}
  			ret.append("}");
  			return ret.toString();
  		}
  		public static void dbg(Object... o) throws Exception {
  			if(LOCAL) {
  				PrintStream ps = new PrintStream("src/Debug.txt");
  				System.setErr(ps);
  				System.err.print("Line #"+Thread.currentThread().getStackTrace()[2].getLineNumber()+": [");
  				for(int i = 0; i<o.length; i++) {
  					if(i!=0) {
  						System.err.print(", ");
  					}
  					System.err.print(ts(o[i]));
  				}
  				System.err.println("]");
  			}
  		}
  	}
  
  }