Polycarp must pay exactly n burles at the checkout. He has coins of two nominal values: 1 burle and 2 burles. Polycarp likes both kinds of coins equally. So he doesn't want to pay with more coins of one type than with the other.

Thus, Polycarp wants to minimize the difference between the count of coins of 1 burle and 2 burles being used. Help him by determining two non-negative integer values c_1 and c_2 which are the number of coins of 1 burle and 2 burles, respectively, so that the total value of that number of coins is exactly n (i. e. c_1 + 2 ⋅ c_2 = n), and the absolute value of the difference between c_1 and c_2 is as little as possible (i. e. you must minimize |c_1-c_2|).

Input

The first line contains one integer t (1 ≤ t ≤ 10^4) — the number of test cases. Then t test cases follow.

Each test case consists of one line. This line contains one integer n (1 ≤ n ≤ 10^9) — the number of burles to be paid by Polycarp.

Output

For each test case, output a separate line containing two integers c_1 and c_2 (c_1, c_2 ≥ 0) separated by a space where c_1 is the number of coins of 1 burle and c_2 is the number of coins of 2 burles. If there are multiple optimal solutions, print any one.

Example

Input


6
1000
30
1
32
1000000000
5


Output


334 333
10 10
1 0
10 11
333333334 333333333
1 2

Note

The answer for the first test case is "334 333". The sum of the nominal values of all coins is 334 ⋅ 1 + 333 ⋅ 2 = 1000, whereas |334 - 333| = 1. One can't get the better value because if |c_1 - c_2| = 0, then c_1 = c_2 and c_1 ⋅ 1 + c_1 ⋅ 2 = 1000, but then the value of c_1 isn't an integer.

The answer for the second test case is "10 10". The sum of the nominal values is 10 ⋅ 1 + 10 ⋅ 2 = 30 and |10 - 10| = 0, whereas there's no number having an absolute value less than 0.
1
10111
 1
10555
 2
3000002
3000001
 1
3000002

3371 3370
 3519 3518
 1000000 1000001
1000001 1000000
 1000000 1000001

"""
ID: pranav.27
LANG: PYTHON3
TASK: probname
"""
from functools import lru_cache
import copy
import math
import sys

fin = None
fout = None
uabet = ['A', 'B', 'C', 'D', 'E', 'F', 'G', 'H', 'I', 'J', 'K', 'L', 'M', 'N', 'O', 'P', 'Q', 'R', 'S', 'T', 'U', 'V',
         'W', 'X', 'Y', 'Z']
abet = ['a', 'b', 'c', 'd', 'e', 'f', 'g', 'h', 'i', 'j', 'k', 'l', 'm', 'n', 'o', 'p', 'q', 'r', 's', 't', 'u', 'v',
        'w', 'x', 'y', 'z']


def start(filename):
    filename = filename.replace('.py', '')
    global fin
    global fout
    infile = filename + ".in"
    outfile = filename + ".out"
    fin = open(infile)
    fout = open(outfile, "w")


def permutation(lst):
    if len(lst) == 0:
        return []
    if len(lst) == 1:
        return [lst]
    l = []
    for i in range(len(lst)):
        m = lst[i]
        remLst = lst[:i] + lst[i + 1:]
        for p in permutation(remLst):
            l.append([m] + p)
    return l


def subsets(x):
    retset = []
    if len(x) == 0:
        retset = [[]]
    else:
        first = x[-1]
        cop = x.copy()
        cop.remove(first)
        y = subsets(cop)
        retset.extend(copy.deepcopy(y))
        m = copy.deepcopy(y)
        for i in range(len(y)):
            k = m[0]
            m.remove(k)
            k.append(first)
            m.append(k)
        retset.extend(m.copy())
    return retset


class Point:
    def __init__(self, x, y):
        self.x = x
        self.y = y

    def __str__(self):
        return str(self.x) + str(self.y)

    def __hash__(self):
        return hash(str(self))

    def __eq__(self, other):
        return self.x == other.x and self.y == other.y


class frac:
    def __init__(self, n, d):
        self.n = n
        self.d = d

    def __str__(self):
        return str(self.n) + '/' + str(self.d)

    def __hash__(self):
        return hash(str(self))

    def simp(self):
        div = math.gcd(self.n, self.d)
        self.n = self.n / div
        self.d = self.d / div

    def __eq__(self, other):
        return self.n / self.d == other.n / other.d

    def __lt__(self, other):
        return self.n / self.d < other.n / other.d


class Interval:
    def __init__(self, start, end):
        self.start = start
        self.end = end

    def __str__(self):
        return str(self.start) + str(self.end)

    def __hash__(self):
        return hash(str(self))

    def __eq__(self, other):
        return self.start == other.start and self.end == other.end

    def __lt__(self, other):
        return self.start < other.start


class Graph():
    def __init__(self, vertices):
        self.V = vertices
        self.graph = [[0 for column in range(vertices)]
                      for row in range(vertices)]

    def minDistance(self, dist, sptSet):
        min = sys.maxsize
        min_index = -1
        for v in range(self.V):
            if dist[v] < min and sptSet[v] == False:
                min = dist[v]
                min_index = v
        if min_index == -1:
            for v in range(self.V):
                if not sptSet[v]:
                    min_index = v
                    break
        return min_index

    def dijkstra(self, src):
        dist = [sys.maxsize] * self.V
        dist[src] = 0
        sptSet = [False] * self.V
        for cout in range(self.V):
            u = self.minDistance(dist, sptSet)
            sptSet[u] = True
            for v in range(self.V):
                if self.graph[u][v] > 0 and sptSet[v] == False and dist[v] > dist[u] + self.graph[u][v]:
                    dist[v] = dist[u] + self.graph[u][v]

        return dist


def overlap(verl1, verl2):
    if verl1.end >= verl2.start:
        return True
    else:
        return False


def merge(verl1, verl2):
    retverl = Interval(min(verl1.start, verl2.start), max(verl1.end, verl2.end))
    return retverl


def changeBase(num, base):
    if base == 2:
        return "{0:b}".format(num)
    power = math.floor(math.log(num, base))
    remainder = num
    end = []
    iter = list(range(power + 1))
    iter.reverse()
    for i in iter:
        if remainder >= base ** i:
            q, r = divmod(remainder, base ** i)
            end.append(q)
            remainder = r
        else:
            end.append(0)
    retlist = []
    for i in end:
        if i > 9:
            retlist.append(uabet[i - 10])
        else:
            retlist.append(i)
    retlist = map(str, retlist)
    return ''.join(retlist)


def prime(num):
    if num == 2:
        return True
    if num % 2 == 0:
        return False
    for i in range(2, math.ceil(num ** 0.5) + 1):
        if num % i == 0:
            return False
    return True

def solve(n):
    if n%3 == 0:
        x = n//3
        return str(x)+' '+str(x)
    if n%3==1:
        x=n//3
        return str(x+1)+' '+str(x)
    if n%3==2:
        x = n//3
        return str(x)+' '+str(x+1)



def main():
    t = int(input())
    for i in range(t):
        n = int(input())
        print(solve(n))


# code timer

main()
