問題一覧 > 通常問題

No.3127 Multiple of Twin Prime

レベル : / AI推定難易度 : 850 / 実行時間制限 : 1ケース 2.500秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : (AC するまで非表示) / 解いたユーザー数 130
作問者 : 👑 loop0919 / テスター : Apollo@Kuro Iroha_3856 ルク nikoro256 lif4635
お気に入りにしたユーザー ProblemId : 11856 / 自分の提出
問題文最終更新日: 2026-01-07 22:54:24
This statement was translated by AI (claude-opus-5-5, effort medium) and may contain errors or differ in nuance from the original. The original statement takes precedence. Back to the original
yukicoder contest 465 (順位表) の他の問題:

Problem Statement

When both $p, p + 2$ are prime, the pair is called twin primes.

We define an integer $n$ that can be expressed as $n = p \times (p + 2)$ using a prime $p$ and a prime $p + 2$ as a "product of twin primes".

You are given an integer $N$. Find the largest "product of twin primes" that is at most $N$.
However, if there is no "product of twin primes" at most $N$, output -1.

You are given $T$ test cases; answer each of them.

Constraints

  • $1 \leq T \leq 10^5$
  • $1 \leq N \leq 10^{14}$
  • All input values are integers

Input

The input is given from standard input in the following format. Here, $\mathrm{case}_i ~ (i = 1, 2, \cdots, T)$ is the $i$-th test case.

$T$
$\mathrm{case}_1$
$\mathrm{case}_2$
$\vdots$
$\mathrm{case}_T$

Each test case is given in the following format.

$N$

Output

Output $T$ lines. On the $i$-th line, output the answer to the $i$-th test case.

For each test case, output the largest "product of twin primes" that is at most $N$. However, if there is no "product of twin primes" at most $N$, output -1.

Sample

Sample
Input
6
16
5
143
425
998244353
100000000000000
Output
15
-1
143
323
994897763
99999440000783

The following holds for the $1$-st through $3$-rd test cases.

  • For the $1$-st test case, the largest "product of twin primes" at most $16$ is $15 = 3 \times 5$.
  • For the $2$-nd test case, there is no "product of twin primes" at most $5$.
  • For the $3$-rd test case, the largest "product of twin primes" at most $143$ is $143 = 11 \times 13$.

提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。