### 问题描述

给定一个正整数 $n$，且已知 $n!%3^m==0$ $(n!=1\times2\times3...\times n),m$ 为一个非负整数）必成立，问：$m$ 的最大值等于多少？

输入格式

输入第 $1$ 行包含一个正整数 $T$，表示有 $T$ 组测试数据。

第 $2\sim T+1$ 行每行输入一个正整数 $n$。

输出格式

对于每一组测试数据，输出一个整数，表示答案，输出一组数据换一行。

样例输入

3
10
5
12

样例输出

4
1
5

说明/提示

对于所有评测数据，$1\leq T\leq 1000，1\leq n\leq 10^{18}$。