2265 - 素数间隔
Description

有多组数据,每组一个n,若n为质数,输出0.否则输出离它最近的两个质数(一个比n大,一个比n小)。(质数最大为 \leq5 \times 10^6。)


Input

第一行也给数字t,表示t次查询

接下来t个数字n,表示询问!

Output

如果是素数,则输出一个0,如果不是素数,输出两个附近的质数!注意换行

Examples

Input

3
8
12
17

Output

7 11
11 13
0
题目参数
Time Limit 1 second
Memory Limit 128 MB
提交次数 44
通过次数 8