Stone的宝剑

Time Limit: 1000 ms Memory Limit: 65536 KiB

Problem Description

Stone 是山理工闻名校内外的剑客高手。他有 n 把祖传的宝剑,宝剑长度为 1, 2, 3, ..., n。

这天,Stone 与 HYQ 为了 bLue 争风吃醋,约好在 9#409 一决高下,输的人则退出对 bLue 的追求。

Stone 的功力不如 HYQ,但是他有祖传的“三才剑阵”,即三把剑若可以组成三角形,则威力翻三倍。

HYQ 非常害怕 Stone 的“三才剑阵”,所以他决定去偷 Stone 的宝剑,但是 HYQ 害怕被 Stone 发现踪迹,所以他要尽可能偷数量更少的宝剑来节约时间。

现在,HYQ 来询问你,他至少要偷几把宝剑才可使 Stone 组不成“三才剑阵”,若你可答对,则 HYQ 会请你吃 QAQ 的桔子。

Input

多组输入。第一行先输入一个组数 T (1 <= T <= 40)。

接下来有 T 行,每行输入一个 n (1 <= n <= 40),代表 Stone 有 n 把家传宝剑。

Output

对于每组输入,输出一行“QAQ #x: y”,x 代表第几组,y 代表 HYQ 最少需要偷几把剑。

Sample Input

2
4
5

Sample Output

QAQ #1: 1
QAQ #2: 1

Hint

Source

【第六届ACM趣味编程循环赛 Round #3】c~k