🏔️Twin Peaks Contest #01

Bạn có một thằng bạn thân tên là PhuocThien. PhuocThien không bị gì cả, nó chỉ bị OCD nhị phân. Mỗi khi đi ăn, PhuocThien không nhìn giá tiền bằng hệ thập phân mà toàn bí mật đổi nó sang hệ nhị phân. Nếu con số đó không "đối xứng bit" (ví dụ \(101\), \(1001\)), nó sẽ rơi vào trạng thái hoảng loạn, đổ mồ hôi hột và nhất quyết không chịu trả tiền vì cho rằng con số đó "mất cân đối, xúc phạm thị giác".Để cứu vãn tình bạn và cũng là cứu cái dạ dày của mình, bạn phải trở thành "bác sĩ tâm lý" bất đắc dĩ. Với mỗi hóa đơn PhuocThien đưa ra, bạn cần dùng tốc độ ánh sáng để kiểm tra xem nó có "đẹp" lòng PhuocThien không. Nếu có, hãy hô YES để nó bình tĩnh lại và rút ví, còn không thì chuẩn bị tinh thần ăn NO và tự trả tiền.

Ví dụ:

• Số 9 có dạng nhị phân là 1001 -> Là đối xứng.
• Số 5 có dạng nhị phân là 101 -> Là đối xứng.
• Số 10 có dạng nhị phân là 1010 -> Không đối xứng.

Cho số nguyên \(T\) \((1 ≤ T ≤ 10^5)\) là số truy vẫn, với mỗi truy vấn, nhập vào:
Một số \(N\) \((1 ≤ N ≤ 10^9)\)

Yêu cầu: Hãy in ra màn hình "YES" nếu \(N\) là đối xứng bit, ngược lại in ra "NO".

Example

9
11
10
9
5
1
3
7
100
111

NO
NO
YES
YES
YES
YES
YES
NO
NO

Protoype và Lam2012 đã hoàn thành công việc của mình và cùng đi sang nước ngoài để tìm hiểu văn hoá mới, tại đây hai người Protoype và Lam2012 được học sinh gọi là "Giáo sư Ba Lô".

Giáo sư Ba Lô vừa phát minh ra một loại "Kẹo Năng Lượng Số Hóa". Mỗi viên kẹo được mã hóa bằng một số nguyên dương \(N\).
Vì để kích thích bộ não thiên tài của các bạn học sinh, số nguyên dương \(N\) được chuyền thành chuỗi nhị phân \(S\) chỉ gồm các ký tự '0' (vị nhạt nhẽo) và '1' (vị ngọt ngào).

Để kích hoạt hiệu ứng đặc biệt của kẹo, học sinh cần tìm ra các Đoạn Mã Cân Bằng. Một đoạn mã được gọi là "Cân Bằng" nếu nó thỏa mãn hai điều kiện khắt khe sau:

1. Độ dài chẵn: Đoạn mã phải có số lượng ký tự là một số chẵn (để chia đều cho hai người bạn cùng ăn).
2. Sự công bằng tuyệt đối: Nếu ta cắt đôi đoạn mã đó thành hai phần bằng nhau (nửa đầu và nửa sau), thì số lượng vị ngọt ('1') ở nửa đầu phải bằng đúng số lượng vị ngọt ('1') ở nửa sau.

Ví dụ minh họa:

• Xét đoạn mã 1001:
  • Độ dài là \(4\) (chẵn).
  • Nửa đầu là 10 có \(1\) số '1'.
  • Nửa sau là 01 có \(1\) số '1'.
  • Vì \(1 = 1\), nên đây là một đoạn mã cân bằng.
• Xét đoạn mã 1100:
  • Độ dài là \(4\) (chẵn).
  • Nửa đầu là 11 có \(2\) số '1'.
  • Nửa sau là 00 có \(0\) số '1'.
  • Vì \(2 \neq 0\), nên đây KHÔNG phải là đoạn mã cân bằng.

Input

• Dòng đầu tiên chứa số nguyên dương \(T\) (\(1 \le T \le 1000\)) là số lượng truy vẫn.
• T dòng tiếp theo chứa các số nguyên \(N\) (\(1 \le N \le 10^6\)).

Output

• Với mỗi truy vấn in ra "YES" nếu \(N\) là Đoạn Mã Cân Bằng ngược lại in ra "NO".

Example

2
9
12

YES
NO

Scoring

• \(50\%\) số test tương ứng với \(50\%\) số điểm với \(1 \le T \le 1000\).
• \(50\%\) số test còn lại ứng với \(50\%\) số điểm với \(1000 < T \le 10^6\).

Ngồi trong quán net, Protoype huých vai Lam2012 rồi chỉ vào màn hình: "Mày thấy hội Mặt Nạ Hành Xác này chưa? Bọn nó thề không độc thân, ít nhất phải có 2 ước nguyên tố mới chịu chơi. Nhưng cái nết thì cực hãm: gọi \(P\) là tích và \(S\) là tổng các ước nguyên tố phân biệt, thì \(P\) phải chia hết cho \(S\), mà chia xong kết quả \(Q = P/S\) lại phải lộn về làm một số nguyên tố thì mới chịu chốt đơn." Lam2012 nhìn cái giới hạn \(5 \cdot 10^6\) mà muốn sút cho thằng bạn một phát vì cái tội bắt CPU hóa vàng để duyệt trâu. Protoype chỉ cười khà khà: "Dùng não mà nặn số đi con trai, cái hội biến thái này hiếm tới mức đếm chưa hết bàn tay đâu!"

Yêu cầu: Cho đoạn \([L, R]\), hãy đếm các số nguyên dương \(n\) thỏa mãn:

• \(n\) có ít nhất \(2\) ước nguyên tố phân biệt.
• Gọi \(P\) là tích, \(S\) là tổng các ước nguyên tố phân biệt của \(n\). Ta có \(P\) chia hết cho \(S\) và \(Q = P/S\) là một số nguyên tố.

Input

• Dòng đầu tiên chứa số nguyên \(T\) (\(1 \le T \le 10^5\)) — số lượng bộ test.
• \(T\) dòng tiếp theo, mỗi dòng chứa hai số nguyên \(L\) và \(R\) (\(1 \le L \le R \le 5 \cdot 10^6\)).

Output

• Với mỗi bộ test, in ra một số nguyên duy nhất là số lượng số "Siêu Hiếm" trong đoạn \([L, R]\).

Example

3
1 30
30 30
1 1000

1
1
40

Scoring

• Subtask \(1\) (\(25\%\) số điểm): \(T \le 10, L, R \le 10^5\).
• Subtask \(2\) (\(25\%\) số điểm): \(T \le 10, L, R \le 5 \cdot 10^6\).
• Subtask \(3\) (\(25\%\) số điểm): \(T \le 10^5, L, R \le 10^5\).
• Subtask \(4\) (\(25\%\) số điểm): Không có ràng buộc gì thêm.

Prototype rủ PhuocThien và uou chơi một trò hơi “khó chịu”: chọn đúng k số có 2 chữ số sao cho không bị “đụng hàng bản lật” (tức là chọn 12 thì cấm 21, còn mấy số kiểu 33 thì tự loại vì lật lại vẫn là nó), đồng thời tổng các số phải đúng bằng S; nghe thì đơn giản nhưng ba người ngồi tính mãi không ra nên quyết định giao lại cho bạn 😅

Yêu cầu: Cho hai số nguyên dương \(k\) và \(S\). Hãy đếm số lượng tập hợp \(A\) thỏa mãn các điều kiện trên, vì số lượng tập hợp có thể sẽ quá lớn nên ta sẽ lấy kết quả \(mod\) \(10^9 + 7\).

Input

• Một dòng duy nhất chứa hai số nguyên \(k\) và \(S\) (\(1 \le k \le 40, 10 \le S \le 3500\)).

Output

• Một số nguyên duy nhất là số lượng tập hợp thỏa mãn.

Example

2 35

6

Scoring

• Subtask 1 (\(50\%\) điểm): \(k \le 4, S \le 350\).
• Subtask 2 (\(50\%\) điểm): \(k \le 40, S \le 3500\).

Bối cảnh
Tại vương miện số học LQDOJ, Prototype đang canh giữ một dãy gồm \(n\) viên ngọc ma thuật. Mỗi viên ngọc có một mức năng lượng là \(a_i\). Tuy nhiên, phù thủy uou đã thực hiện một lời nguyền cổ xưa lên dãy ngọc này. Lời nguyền mang tên "Sự suy tàn của Phi". Mỗi khi uou vung trượng, năng lượng của các viên ngọc trong một phạm vi nhất định sẽ bị hấp thụ và biến đổi theo quy tắc của hàm Phi Euler. Năng lượng sẽ giảm dần cho đến khi chạm mức tối thiểu là 1 — lúc đó viên ngọc sẽ trở thành một viên đá bình thường và không thể bị hút thêm năng lượng được nữa.
Nhiệm vụ của bạn
Bạn vào vai một nhà tiên tri. Prototype liên tục hỏi bạn về tổng năng lượng còn lại của một đoạn ngọc để chuẩn bị cho cuộc phản công. Bạn phải phản hồi thật nhanh trước khi uou hoàn tất lời nguyền.

Input

• Dòng 1: \(n\) và \(q\) (\(n, q \le 2 \cdot 10^5\)).
• Dòng 2: \(n\) số nguyên \(a_1, a_2, \dots, a_n\) (\(a_i \le 10^6\)) — năng lượng ban đầu của \(n\) viên ngọc.
• \(q\) dòng tiếp theo là các truy vấn:
  • \(1 \ l \ r\) : uou tung lời nguyền, tất cả viên ngọc từ vị trí \(l\) đến \(r\) bị biến đổi: \(a_i = \phi(a_i)\).
  • \(2 \ l \ r\) : Prototype hỏi tổng năng lượng từ vị trí \(l\) đến \(r\).

Output

• Với mỗi câu hỏi của Protoype, in ra một số nguyên duy nhất là tổng năng lượng.

Example

4 3
10 10 10 10
2 1 4
1 2 3
2 1 4

40
28

Scoring

• Subtask 1 (\(30\%\) điểm): \(n, q ≤ 1000, a ≤ 10^3\).
• Subtask 2 (\(20\%\) điểm): \(n, q ≤ 2 ⋅ 10^5, a ≤ 2\).
• Subtask 3 (\(50\%\) điểm): \(n, q ≤ 2 ⋅ 10^5, a ≤ 10^6\).