Hash Table(雜湊表)的時間複雜度完全建立在資料的分散程度。假如很多資料都擠在同一格，那他搜尋就需要花上O(n)；反之如果每個資料都分散在不同格，那他搜尋只需要O(1)就可以了。有證明指出當Hash Table的大小如果是質數，那資料會比非質數還分散！證明的話交給數學系就好，資工系只要會用就可以了。現在你想要建一個大小約為n的Hash Table，請你找到離n最近的質數。
有多組測資。
每組測資有一個正整數N，2≤N≤1000000
對於每組測資，請輸出離N最近的質數。
如果兩個質數與N的距離相同，則輸出比較大的那個質數。