TopCoder

Thumb 1800
weyryafjnm;
erfvjuaweikm

User's AC Ratio

97.2% (35/36)

Submission's AC Ratio

30.5% (73/239)

Tags

Description

相信大家都對質數這種特殊的正整數不陌生: 一個大於1的自然數中,除了1和此整數自身外,沒辦法被其他自然數整除的數;

即只有兩個正因數(1和自己)的自然數,就是質數。

如果一個質數在將其所有位數顛倒 (reverse)後仍是一個質數,那麼我們就稱這個數是「Emirp」(中文譯作「反質數」),

而這個名字的由來也很容易能理解。(Emirp 正是質數的英文 Prime 反過來書寫的結果)

※舉例來說:

17 是質數,而將其每位數反轉後我們得到 71 ,而 71 恰好也是質數。因此,17 是一個 Emirp 。
同理,71 也必然是 Emirp 。

--
現在,請你寫一個程式,找出由小到大數來第 n 個 Emirp 是哪個數。

(注意 : 在這個問題中,3, 5, 7, 11, 191 這類「迴文質數」由於反轉前後的結果一樣,因此我們將其視為 Emirp。)

Input Format

第一行有一個正整數 T (1≦T≦1000),代表以下共有幾筆測試資料。

對於每一筆測試資料,給定一個正整數 n (1≦n≦100000),請輸出第 n 個 Emirp 是多少。

Output Format

對於每一筆測試資料,請輸出一行,代表第 n 個 Emirp。

Sample Input

Sample Case #1:

2
1
2

Sample Case #2:

1
4

Sample Output

Sample Case #1:

13
17

Sample Case #2:

37

Hints

小於 100 的 Emirp 包括: 13, 17, 31, 37, 71, 73, 79, 97

Problem Source

原TIOJ1535 / Problem Setter: Skyly

Subtasks

No. Testdata Range Score
1 0 20
2 1 20
3 2 20
4 3 20
5 4 20

Testdata and Limits

No. Time Limit (ms) Memory Limit (KiB) Output Limit (KiB) Subtasks
0 5000 65536 262144 1
1 5000 65536 262144 2
2 5000 65536 262144 3
3 5000 65536 262144 4
4 5000 65536 262144 5