32. 數質數

數質數

題目敘述

普奇是一個很喜歡質數的人，質數是除了一與自己外不能被整除的數，這樣的數字十分有趣，而他最常做的事是數質數，他覺得數質數能幫助他冷靜。

但是每次從最小的質數開始數對他來說有點無聊了，他希望能從第s小的質數開始數，數到第t小的，請你幫幫他數出這些質數。

輸入說明

第一行有一個數字$T \leq 1009$， 接下來T行，每行有兩個數字s, t。

輸出說明

對每筆測資，輸出第s小到第t小的質數，以一格空白隔開，數列最後不能有多餘空白。

範例輸入

3 1 3 2 5 3 7

範例輸出

2 3 5 3 5 7 11 5 7 11 13 17

子題一[17%]

$1 \leq s \leq t \leq 100003, s = t$

子題二[23%]

$1 \leq s \leq t \leq 100003, 0 \leq t - s \leq 11$

子題三[29%]

$1 \leq s \leq t \leq 100003, 0 \leq t - s \leq 107$

子題四[31%]

$1 \leq s \leq t \leq 100003, 0 \leq t - s \leq 1013$

Judge Setting

run-time limit: 1000 ms
memory limit: 104857600 byte
測資數量: 3