Description
一般的河內塔想必大家一定覺得很無聊 , 於是某人發明了一個遊戲. 這遊戲有N根柱子和許多的球 , 每個球上面有編號1,2,3…這些看起來很普通的球卻充滿了魔力!如果放在"同一根柱子上相鄰"的兩個球編號和不是一個平方數的話 , 那就會爆炸!!!比如說3號可以在1號上面 , 因為1+3 = 4是一個平方數. 但是2號就不能在1號上面了 , 因為1+2 = 3不是一個平方數!!
玩遊戲的人每次必須按照1,2,3…的順序將球放到柱子上 , 直到他無法再放下任何一顆球. 你的任務就是判斷有N根柱子時 , 玩遊戲的人能放下多少顆球呢?
下面這張圖是4根柱子時最好的放置狀態 (11顆球)
Input
測資的第一行為一個正整數T , 代表之後會有T筆測資.
接下來T行 , 每行會有一個正整數N (1<=N<=50) , 代表有N根柱子可以使用.
Output
每組測資輸出一行 , 為N根柱子能最多放入幾顆球.