Các số nguyên tố liệt kê theo thứ tự tăng dần \(2, 3, 5, 7, 11, 13, \dots\) tạo thành một dãy số và đánh số bắt đầu từ \(1\). Gọi \(p_i\) là số nguyên tố thứ \(i\), ta nói \(p_i\) là số nguyên tố đối xứng nếu nó bằng trung bình cộng của 2 số nguyên tố liền trước và liền sau nó. Nói cách khác \(p_i\) là số nguyên tố đối xứng nếu thỏa điều kiện:
\(\(p_i = \frac{p_{i-1} + p_{i + 1}}{2}\)\)

Như vậy, 10 số nguyên tố đối xứng đầu tiên là: \(5, 53, 157, 173, 211, 257, 263, 373, 563, 593\).

Yêu cầu: cho số nguyên \(n\). Cho biết \(n\) có phải số nguyên tố đối xứng hay không.

Input:

• Dòng đầu tiên ghi số nguyên \(t (1 ≤ t ≤ 10^5)\) – số lượng số \(n\) cần kiểm tra.
• \(t\) dòng tiếp theo, mỗi dòng ghi một số nguyên \(n (1 ≤ n ≤ 2 * 10^7)\)

Output: gồm \(t\) dòng, mỗi dòng ghi “YES” hoặc “NO” là câu trả lời tương ứng với câu hỏi trong input.

Sample Input:

3
11
5
373

Sample Output:

NO
YES
YES

Không biết các bài toán đa cấp có được cho vào chung một contest hay không, nhưng sau đây là một bài toán như thế:

CAO (Chief Air-conditioner Officer) của The Pyramid Company trực thuộc tập đoàn VierTech phát cho mỗi nhân viên tập sự một hình tam giác trống, gọi là tam giác cấp 0.

Khi một nhân viên mời đủ 3 người khác tham gia tập đoàn, tam giác của nhân viên đó sẽ được nâng lên cấp 1: Từ tam giác cấp 0, lấy trung điểm của 3 cạnh tam giác nối lại với nhau, chia hình cũ thành 4 hình tam giác cấp 0 nhỏ hơn.

Khi 3 người đó tiếp tục mời thêm 3 người nữa, các tam giác tiếp tục chia nhỏ như vậy, sẽ ra tam giác cấp 2 (gồm 4 hình tam giác cấp 1), cấp 3 (gồm 4 hình tam giác cấp 2), …

Lương của một nhân viên (tính bằng BTC) bằng số điểm trên tam giác mà nhân viên có. Theo hình ta thấy, lương bậc 0 là 3 BTC, bậc 1 là 6 BTC, ...

Vì là công ty đa cấp nên bạn KHÔNG CẦN BẰNG CẤP, chỉ cần có KHÁT KHAO LÀM GIÀU thì sẽ GIÀU NHANH. Cũng chẳng cần học toán, vì vậy khá nhiều nhân viên không biết lương của họ là bao nhiêu.

Một nhân viên cho bạn xem tam giác họ có, muốn nhờ bạn tính họ sẽ có bao nhiêu tiền. Tính giúp họ đê 😛

Input

• 1 dòng duy nhất gồm một số \(n\) là cấp của tam giác mà người hỏi sở hữu

Output

• Lương của người đó, tính bằng Satoshi, modulo \(10^9+7\)

Scoring

• Subtask \(1\) (\(15\%\) số điểm): \(n \le 20\)
• Subtask \(2\) (\(45\%\) số điểm): \(n \le 10^6\)
• Subtask \(3\) (\(40\%\) số điểm): \(n \le 10^{18}\)

Example

2

15

Xâu \(x\) được gọi là lớn hơn xâu \(y\) nếu xâu \(y\) là đoạn đầu của xâu \(x\) hoặc xét kí tự đầu tiên khác nhau thì kí tự của xâu \(x\) lớn hơn kí tự của xâu \(y\).

Để luyện tập về việc so sánh hai xâu, Hồng đã tạo ra bài toán sau: Từ hai số nguyên dương \(a,b (a < b)\), tạo ra một dãy số gồm \(b - a + 1\) số: \(a, a + 1, ... , b\). Sau đó, sắp xếp lại các số theo thứ tự từ điển (coi mỗi số là một xâu và sắp xếp tăng dần) bằng các thao tác như sau: Mỗi lần chọn
và lấy ra một số trong dãy rồi chèn lại vào dãy ở vị trí bất kì.

Ví dụ, nếu \(a = 9, b = 11\) ta có dãy số gồm \(3\) số \(9, 10, 11\), dãy số được sắp xếp theo thứ tự từ điển là \(10, 11, 9\) và cần ít nhất một thao tác (rút số \(9\) khỏi dãy và chèn vào cuối dãy).

Yêu cầu: Cho hai số nguyên dương \(a, b (a < b)\), hãy tính số thao tác ít nhất để sắp xếp các số \(a, a + 1, ... , b\) theo thứ tự từ điển.

Input

• Vào từ thiết bị vào chuẩn gồm một dòng chứa hai số nguyên dương \(a, b (a < b \le 10^9)\)

Output

• Ghi ra thiết bị ra chuẩn gồm một dòng chứa một số nguyên là số thao tác ít nhất để sắp xếp các số \(a, a + 1, ... , b\) theo thứ tự từ điển.

Scoring

• Subtask \(1\) (\(20\%\) số điểm): \(b - a = 1\);
• Subtask \(2\) (\(20\%\) số điểm): \(b - a \le 10\);
• Subtask \(3\) (\(30\%\) số điểm): \(b − a \le 1000\);
• Subtask \(4\) (\(30\%\) số điểm): \(b − a \le 10^5\);

Example

9 11

1

Một bài toán khó trong danh sách các bài mà Hồng lựa chọn để tập huấn cho các em học sinh khóa
dưới như sau:

Cho hai số nguyên dương \(n, t\),cần tìm một bộ gồm ít số nguyên dương nhất, giả sử bộ tìm được gồm \(k\) số nguyên dương \(a_1, a_2,..., a_k\) thì:

Yêu cầu: Cho \(2\) số nguyên dương \(n, t\), hãy tìm số nguyên dương \(k\) thoả mãn.

Input

• Vào từ thiết bị vào chuẩn gồm một dòng chứa hai số nguyên \(n, t (n, t \le 1000)\)

Output

• Ghi ra thiết bị ra chuẩn gồm một dòng chứa số nguyên \(k\) là số lượng số ít nhất để tồn tại bộ gồm \(k\) số nguyên dương thoả mãn, nếu không tồn tại ghi số \(-1\).

Example

4 1

2