该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

竹子生长周期短，四季常青，常作为城市绿化植物，因其不畏严寒酷暑，不畏风霜雪欺，得到了人们的广泛喜爱。 但是由于人类对环境的破坏，导致全球环境变化，不适于竹子的生长。 作为生物学家的你在一次外出中找到了全球仅剩的一株竹子幼株。你希望好好保护这株竹子，于是你费劲心思研发了一种培养液，将竹子幼株侵泡后便可以在环境中正常生存了。

并且你通过大量计算分析，发现竹子生长到第 5 年就能成为一株成熟的竹子，每一株成熟的竹子每年可以萌发 3 株幼株。对此你很是高兴，并且你想要知道最早在第几年的时候竹子数量能达到 n 株。

Input

第一行一个正整数 T，表示 T 组数据。

每组数据输入一行一个整数 n。

Output

每组数据输出一行一个整数 y，表示最早在第 y 年的时候竹子数量能达到 n 株。

Examples

3
4
5
20

5
6
9

Notes

$T\in [1,10], n\in[1,9223372036854775807]$