def solution(n):
count = 0
for i in range(12, -1, -1):
pw = 3 ** i
if n - pw < 0:
continue
n -= pw
count += 1
return count
if __name__ == "__main__":
from sys import stdin
t = int(stdin.readline())
for _ in range(t):
n = int(stdin.readline())
print(solution(n))
ZGVmIHNvbHV0aW9uKG4pOgogICAgY291bnQgPSAwCgogICAgZm9yIGkgaW4gcmFuZ2UoMTIsIC0xLCAtMSk6CiAgICAgICAgcHcgPSAzICoqIGkKICAgICAgICBpZiBuIC0gcHcgPCAwOgogICAgICAgICAgICBjb250aW51ZQogICAgICAgIG4gLT0gcHcKICAgICAgICBjb3VudCArPSAxCgogICAgcmV0dXJuIGNvdW50CgoKaWYgX19uYW1lX18gPT0gIl9fbWFpbl9fIjoKICAgIGZyb20gc3lzIGltcG9ydCBzdGRpbgogICAgdCA9IGludChzdGRpbi5yZWFkbGluZSgpKQogICAgCiAgICBmb3IgXyBpbiByYW5nZSh0KToKICAgICAgICBuID0gaW50KHN0ZGluLnJlYWRsaW5lKCkpCiAgICAgICAgcHJpbnQoc29sdXRpb24obikpCg==