A card pyramid of height 1 is constructed by resting two cards against each other. For h>1, a card pyramid of height h is constructed by placing a card pyramid of height h-1 onto a base. A base consists of h pyramids of height 1, and h-1 cards on top. For example, card pyramids of heights 1, 2, and 3 look as follows:

<image>

You start with n cards and build the tallest pyramid that you can. If there are some cards remaining, you build the tallest pyramid possible with the remaining cards. You repeat this process until it is impossible to build another pyramid. In the end, how many pyramids will you have constructed?

Input

Each test consists of multiple test cases. The first line contains a single integer t (1≤ t≤ 1000) — the number of test cases. Next t lines contain descriptions of test cases.

Each test case contains a single integer n (1≤ n≤ 10^9) — the number of cards.

It is guaranteed that the sum of n over all test cases does not exceed 10^9.

Output

For each test case output a single integer — the number of pyramids you will have constructed in the end.

Example

Input


5
3
14
15
24
1


Output


1
2
1
3
0

Note

In the first test, you construct a pyramid of height 1 with 2 cards. There is 1 card remaining, which is not enough to build a pyramid.

In the second test, you build two pyramids, each of height 2, with no cards remaining.

In the third test, you build one pyramid of height 3, with no cards remaining.

In the fourth test, you build one pyramid of height 3 with 9 cards remaining. Then you build a pyramid of height 2 with 2 cards remaining. Then you build a final pyramid of height 1 with no cards remaining.

In the fifth test, one card is not enough to build any pyramids.
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStream;
import java.io.PrintWriter;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashMap;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Stack;
import java.util.StringTokenizer;

//import hacker51.FastReader;

public class two_pointers_method {
	static class FastReader 
    { 
        BufferedReader br; 
        StringTokenizer st; 
        public FastReader() 
        { 
            br = new BufferedReader(new
                     InputStreamReader(System.in)); 
        } 
        String next() 
        { 
            while (st == null || !st.hasMoreElements()) 
            { 
                try
                { 
                    st = new StringTokenizer(br.readLine()); 
                } 
                catch (IOException  e) 
                { 
                    e.printStackTrace(); 
                } 
            } 
            return st.nextToken(); 
        } 
        int nextInt() 
        { 
            return Integer.parseInt(next()); 
        } 
        long nextLong() 
        { 
            return Long.parseLong(next()); 
        } 
        double nextDouble() 
        { 
            return Double.parseDouble(next()); 
        } 
        String nextLine() 
        { 
            String str = ""; 
            try
            { 
                str = br.readLine(); 
            } 
            catch (IOException e) 
            { 
                e.printStackTrace(); 
            } 
            return str; 
        }
    }
	
	public static void main(String[] args) {
		OutputStream outputStream =System.out;
	    PrintWriter out =new PrintWriter(outputStream);
	FastReader s=new FastReader();
//	int n=s.nextInt();
//	long sum=s.nextLong();
//	long[] a=new long[n];
//	for(int i=0;i<n;i++) {
//		a[i]=s.nextLong();
//	}
//	int l=0;
//	long res=(long) 1e12;
//	long x=0;
//	for(int r=0;r<n;r++) {
//		x+=a[r];
//		while(x>sum) {
//			x-=a[l];
//			l++;
//		}
//		if(x==sum) {
//			res=Math.min(r-l+1, res);
//		}
//	}
//	System.out.println(res);
	int t=s.nextInt();
	while(t>0) {
		long count=0;
		long n=s.nextLong();
				while(n>1) {
					long d=(long) Math.sqrt(24*n+1);
					d-=1;
					d/=6;
					long f=(3*d*d+d)/2;
//					f/=2;
					n-=f;
					count++;	
				}
				out.println(count);
	t--;
	}
out.close();
	}
	static boolean ok(long n) {
		long sum=0;
		while(n>0) {
			sum+=n%10;
			n/=10;
		}
		return (sum==10);
	}
	public static int lower_bound(long[] a ,int n,long x) {
		int l=-1;
		int r=n+1;
		while(r>l+1) {
			int mid=(l+r)/2;
			if(a[mid]<=x) {
				l=mid;
			}else {
				r=mid;
			}
		}
		return l;
				
	}
	public static long longest_Segment_sum_less_than_equal_to_S(long[] a,long sum,int n) {
		int l=0;
		long x=0;
		long res=0;
		for(int r=0;r<n;r++) {
			x+=a[r];
			while(x>sum) {
				x-=a[l];
			l++;
			}
			res=Math.max(r-l+1,res);
		}
		return res;
	}
	public static long shortest_Segment_sum_greater_than_equal_to_S(long[] a,long sum,int n) {
		int l=0;
		long x=0;
		long res=Integer.MAX_VALUE;
		for(int r=0;r<n;r++) {
			x+=a[r];
			while(x-a[l]>=sum) {
				x-=a[l];
				l++;
			}
			if(x>=sum) {
				res=Math.min(res, r-l+1);
			}
		}
		return res;
	}
	public static long total_Segment_sum_less_than_equal_to_S(long[] a,long sum,int n) {
	
		int l=0;
		long x=0;
		long res=0;
		for(int r=0;r<n;r++) {
			x+=a[r];
			while(x>sum) {
				x-=a[l];
				l++;
			}
			res+=((r-l+1));
		}
		return res;
	}
	public static long total_Segment_sum_greater_than_equal_to_S(long[] a,long sum,int n) {
		
		int l=0;
		int l1=-1;
		int r1=-1;
		long x=0;
		long res=0;
		for(int r=0;r<n;r++) {
			x+=a[r];
			while(x-a[l]>=sum) {
				x-=a[l];
				l++;
			}
			if(x>=sum && l!=l1 && r!=r1) {
				res+=(long)(l-l1)*(n-r);
				l1=l;
//				System.out.println(l+" "+l1+" "+r+" "+r1);
			}
			r1=r;
		}
		return res;
	}
	public static long total_Segment_unique_elements_less_than_equal_to_S(long[] a,long k,int n) {
		int l=0;
//		int r=0;
		int count=0;
		long res=0;
		int[] ct=new int[100001];
		for(int r=0;r<n;r++) {
			ct[(int) a[r]]++;
			if(ct[(int) a[r]]==1) {
				count++;
			}
				while(count>k) {
					ct[(int) a[l]]--;
					if(ct[(int) a[l]]==0) {
						count--;
					}
					l++;
				}
				res+=(r-l+1);
			
		}
		return res;
		
	}
	public static long segment_with_maximum_spread(long[] a,int n,long k)
	{
		int l=0;
		long count=0;
	for(int r=0;r<n;r++) {
		add(a[r]);
		while(!good(k)) {
			remove();
			l++;
		}
		count+=r-l+1;
//		System.out.println(r+" "+l);
	}
		return count;
	}
	
public static class Stack1{
	
	private  Stack<Long> st;
	private  Stack<Long> smin;
	private  Stack<Long> smax;
Stack1(){
	this.st=new Stack<>();
	this.smin=new Stack<>();
	this.smax=new Stack<>();
	this.smin.add(Long.MAX_VALUE);
	this.smax.add(Long.MIN_VALUE);
}	 
	
}
static Stack1 st1=new Stack1();
static Stack1 st2=new Stack1();
static void add(long d) {
	st2.st.add(d);
	st2.smin.add(Math.min(d, st2.smin.peek()));
	st2.smax.add(Math.max(st2.smax.peek(),d));
}
static void remove() {
	if(st1.st.isEmpty()) {
		while(!st2.st.isEmpty()) {
			st1.st.add(st2.st.pop());
			st2.smin.pop();
			st2.smax.pop();
			st1.smax.add(Math.max(st1.smax.peek(), st1.st.peek()));
			st1.smin.add(Math.min(st1.smin.peek(), st1.st.peek()));
		}}
		st1.st.pop();
		st1.smax.pop();
		st1.smin.pop();
	
}
static boolean good(long k) {
	long min=Math.min(st1.smin.peek(), st2.smin.peek());
	long max=Math.max(st1.smax.peek(), st2.smax.peek());
	return max-min<=k;
}



public static class Stack2{
	
	private  Stack<Long> st;
	private  Stack<Long> gcd;
Stack2(){
	this.st=new Stack<>();
	this.gcd=new Stack<>();
	gcd.add((long) 0);
}	 
	
}
static Stack2 st3=new Stack2();
static Stack2 st4=new Stack2();
static void add2(long d) {
	st4.st.add(d);
	st4.gcd.add(GCD(st4.gcd.peek(),d));
}
static void remove2() {
	if(st3.st.isEmpty()) {
		while(!st4.st.isEmpty()) {
			st3.st.add(st4.st.pop());
			st4.gcd.pop();
			st3.gcd.add(GCD(st3.gcd.peek(),st3.st.peek()));
			
		}}
		st3.st.pop();
		st3.gcd.pop();
	
}
static boolean good2() {
	if(st3.st.isEmpty()) {
		while(!st4.st.isEmpty()) {
			st3.st.add(st4.st.pop());
			st4.gcd.pop();
			st3.gcd.add(GCD(st3.gcd.peek(),st3.st.peek()));
			
		}}
	long d=st3.gcd.pop();
	long g=st3.gcd.peek();
	st3.gcd.add(d);
	return GCD(g,st4.gcd.peek())==1;
}


public static long GCD(long a,long b) {
	if(b==(long)0) {
		return a;
	}
	return GCD(b , a%b);
}
public static boolean good3() {
	return GCD(st3.gcd.peek(),st4.gcd.peek())==1;
}
public static long shortest_Segment_gcd_equal_to_one(long[] a,int n) {
	int l=0;
	long x=0;
	long res=Integer.MAX_VALUE;
	for(int r=0;r<n;r++) {
		add2(a[r]);
		while(good2()) {
		remove2();
			l++;
		}
		if(good3()) {
			res=Math.min(res, r-l+1);
		}
	}
	return res;
}
public static long[] merge_sort(long[] A, int start, int end) {
	if (end > start) {
		int mid = (end + start) / 2;
		long[] v = merge_sort(A, start, mid);
		long[] o = merge_sort(A, mid + 1, end);
		return (merge(v, o));
	} else {
		long[] y = new long[1];
		y[0] = A[start];
		return y;
	}
}
public static long[] merge(long a[], long b[]) {
//	int count=0;
	long[] temp = new long[a.length + b.length];
	int m = a.length;
	int n = b.length;
	int i = 0;
	int j = 0;
	int c = 0;
	while (i < m && j < n) {
		if (a[i] > b[j]) {
			temp[c++] = a[i++];
		
		} else {
			temp[c++] = b[j++];
		}
	}
	while (i < m) {
		temp[c++] = a[i++];
	}
	while (j < n) {
		temp[c++] = b[j++];
	}
	return temp;
}
}
