小可魚有 N 顆糖果，他把它們排成一排並且由左到右依序編號為 1, 2, 3, ..., N。每一次小可魚都把編號為平方數的糖果全部拿出來吃掉，並且把剩下的糖果依照順序重新排好，並且重新編號 1, 2, 3 ...。考考你，最後一顆被吃掉的糖果，一開始的編號是多少？
輸入的第一行有一個整數 T (1<=T<=1000) 表示有幾組測資。
每一組測試資料的第一行有一個整數 N (1<=N<=109)，代表一開始有幾顆糖果。
對於每一筆測試資料請輸出最後一顆被吃掉的糖果原本的編號是什麼。
5 9 20 5265 20111223 1
7 17 5257 20110741 1
Migrated from old NTUJ.
topcoder
| No. | Testdata Range | Score |
|---|