Problem

Giờ ra chơi, nhóm bạn của bạn bày trò mã hoá để nhắn tin mà thầy cô không hiểu
Luật chơi như sau: mỗi tin nhắn là một số ~n~ ở hệ thập phân (cơ số 10). Bạn phải đổi nó sang hệ cơ số ~b~ để thành mật mã.

Vì nhóm bạn lười viết dài dòng nên quy ước ký tự cho các chữ số như này:

• 0..9 dùng cho giá trị 0..9
• A..Z dùng cho giá trị 10..35
  (ví dụ: 10 -> A, 15 -> F, 35 -> Z)

Nhiệm vụ của bạn: với mỗi test, hãy in ra biểu diễn của ~n~ trong hệ cơ số ~b~ (chỉ dùng chữ in hoa), không có số 0 ở đầu.

Input

Dòng đầu là số bộ test ~t~.
Mỗi test gồm một dòng chứa hai số nguyên ~n, b~:

• ~1 \le n~
• ~2 \le b \le 36~

Output

Với mỗi test, in ra một dòng là biểu diễn của ~n~ trong hệ cơ số ~b~.

Sample

Problem

Trong Thư Khố Cửu Ấn, mỗi hiện vật được gắn với một số nguyên dương ~x~. Người gác kho chỉ cho phép những hiện vật "đúng chuẩn" đi qua nếu ~x~ có chính xác 9 ước số dương (tính cả ~1~ và ~x~).

Bạn được cung cấp một số nguyên ~n~. Hãy đếm xem có bao nhiêu số nguyên dương ~x~ thỏa mãn:

• ~1 \le x \le n~
• ~x~ có đúng 9 ước số dương

In ra số lượng đó.

Input

Một dòng duy nhất chứa số nguyên ~n~ ~(1 \le n \le 10^{12})~.

Output

In ra một số nguyên — số lượng các số ~x~ không vượt quá ~n~ có đúng 9 ước số dương.

Sample

Problem

Chiến tranh đã bùng nổ! Bạn là tổng tư lệnh và phải nhanh chóng bố trí quân để phòng thủ được nhiều căn cứ nhất trước khi địch tấn công.

Có ~n~ căn cứ nằm thẳng hàng và được đánh số từ ~1~ đến ~n~. Căn cứ thứ ~k~ là tổng hành dinh (home base) của bạn.

• Ban đầu (trước ngày 1), chỉ có 1 binh sĩ đang ở căn cứ ~k~.
• Mỗi ngày, các sự kiện xảy ra theo đúng thứ tự như sau:

1) Ra lệnh di chuyển
Bạn chọn một căn cứ ~i~ ~(1 \le i \le n)~ và chọn bất kỳ số lượng binh sĩ đang có trong căn cứ đó (có thể chọn ~0~, hoặc chọn tất cả).
Sau đó, bạn ra lệnh cho toàn bộ những binh sĩ đã chọn cùng di chuyển một hướng:

• hoặc sang căn cứ ~i-1~,
• hoặc sang căn cứ ~i+1~.

Lưu ý:

• Tất cả binh sĩ được chọn trong ngày đó phải đi cùng một hướng.
• Không binh sĩ nào được phép đi ra ngoài dãy:
  • không được đi sang trái của căn cứ ~1~,
  • không được đi sang phải của căn cứ ~n~.

2) Tiếp viện xuất hiện
Sau khi việc di chuyển ở bước (1) kết thúc, sẽ có 1 binh sĩ mới tiến vào căn cứ ~k~.
Binh sĩ mới này không thể bị điều khiển bởi lệnh trong ngày hiện tại (chỉ có thể bị điều khiển từ các ngày sau).

Bạn chỉ có đúng ~m~ ngày để chuẩn bị. Một căn cứ được gọi là đã được củng cố (fortified) nếu có ít nhất 1 binh sĩ đang đóng tại đó.

Nhiệm vụ của bạn: Hãy tính số lượng căn cứ được củng cố lớn nhất (tính cả căn cứ ~k~) mà bạn có thể đạt được vào cuối ngày thứ ~m~.

Input

Dòng đầu là số bộ test ~t~ ~(1 \le t \le 10^4)~.

Mỗi test gồm một dòng chứa ba số nguyên lần lượt là ~n, m, k~:

• ~1 \le k \le n \le 10^5~ — vị trí tổng hành dinh và số căn cứ,
• ~1 \le m \le 10^9~ — số ngày chuẩn bị.

Bảo đảm rằng tổng ~n~ qua tất cả test không vượt quá ~2 \cdot 10^5~.

Output

Với mỗi test, in ra số lượng căn cứ được củng cố lớn nhất có thể có vào cuối ngày thứ ~m~.

Sample

Note

Trong test thứ 2, dưới đây là một cách để củng cố được 3 căn cứ:

• Ngày 1: ra lệnh 0 binh sĩ ở căn cứ 3 di chuyển sang căn cứ 2.
  Cuối ngày, có 1 binh sĩ mới tới căn cứ 2
  (lúc này có 2 binh sĩ ở căn cứ 2 và 0 binh sĩ ở các căn cứ khác).

• Ngày 2: ra lệnh 1 binh sĩ ở căn cứ 2 di chuyển sang căn cứ 1.
  Cuối ngày, có 1 binh sĩ mới tới căn cứ 2.
  (lúc này có 2 binh sĩ ở căn cứ 2 và 1 binh sĩ ở căn cứ 1).

• Ngày 3: ra lệnh 2 binh sĩ ở căn cứ 2 di chuyển sang căn cứ 3.
  Cuối ngày, có 1 binh sĩ mới tới căn cứ 2.
  (lúc này có 1 binh sĩ ở căn cứ 1 và 2, và có 2 binh sĩ ở căn cứ 3).

• Khi đó, mỗi căn cứ 1, 2, 3 đều có ít nhất một binh sĩ
  ⇒ đáp án là 3.

Trong test thứ 3, dưới đây là một cách để đạt được 3 căn cứ được củng cố:

• Ngày 1: ra lệnh cho binh sĩ đang có sẵn, di chuyển từ căn cứ 2 sang căn cứ 3.
  Cuối ngày, có 1 binh sĩ mới tới căn cứ 2.

• Ngày 2: ra lệnh cho binh sĩ ở căn cứ 2 di chuyển sang căn cứ 1.
  Cuối ngày, có 1 binh sĩ mới tới căn cứ 2.

• Khi đó, mỗi căn cứ 1, 2, 3 đều có ít nhất một binh sĩ
  ⇒ đáp án là 3.
  Có thể chứng minh rằng không thể có nhiều hơn 3 căn cứ được củng cố vào cuối ngày 2.

Bên dưới là phần giải thích trực quan cho test thứ 3.

Problem

Trong giờ Tin học, cô giáo cho lớp một dãy số nguyên a gồm ~n~ phần tử. Bạn được phép chọn một đoạn liên tiếp (subarray) từ vị trí ~l~ đến ~r~ rồi trộn các số trong đoạn đó bằng phép OR theo bit.

• Phép OR theo bit lấy từng cặp bit tương ứng của hai số:
  • Kết quả bit = 0 chỉ khi cả hai bit đều 0
  • Còn lại thì bit = 1
• Trong C/C++/Java/Python, toán tử OR theo bit là |.

Ví dụ: 10 | 17 = 01010 | 10001 = 11011 = 27.

Với một đoạn liên tiếp a[l..r], ta định nghĩa:

~OR(l,r) = a[l]~ | ~a[l+1]~ | ~...~ | ~a[r]~

Nhiệm vụ của bạn: xét tất cả các đoạn liên tiếp của mảng a, tính giá trị OR của từng đoạn và đếm xem có bao nhiêu giá trị khác nhau.

Input

• Dòng 1: số nguyên ~n~ ~(1 ≤ n ≤ 10^5)~ — số phần tử của mảng.
• Dòng 2: ~n~ số nguyên ~a[1], a[2], ..., a[n]~ ~(0 ≤ a[i] ≤ 10^9)~.

Output

In ra một số nguyên duy nhất: số lượng giá trị OR khác nhau thu được từ tất cả các đoạn con liên tiếp của mảng.

Sample

Giải thích mẫu:

Có tất cả 6 đoạn liên tiếp (ghi dạng (l, r)):

1. (1,1): 1
2. (1,2): 1 | 2 = 3
3. (1,3): 1 | 2 | 3 = 3
4. (2,2): 2
5. (2,3): 2 | 3 = 3
6. (3,3): 3

Các giá trị OR khác nhau là {1, 2, 3} nên kết quả là 3.

Problem

Mùa Tết này, đội Low Cortisol mở một trò đếm số may mắn để giúp Uma bớt stress.

Trong tập số tự nhiên, ta chia các số thành 2 nhóm:

• Nhóm 1: gồm các số nguyên tố.
• Nhóm 2: gồm các số không phải số nguyên tố (hợp số).

Uma có sở thích khá lạ: Uma chỉ thích những số thuộc nhóm 2, nhưng số lượng ước số dương của nó lại thuộc nhóm 1 (trừ số 2).

Bạn được cho nhiều truy vấn dạng đoạn ~[L, R]~. Hãy giúp Uma đếm xem trong đoạn ~[L, R]~ có bao nhiêu số mà Uma thích nhé.

Input

• Dòng đầu tiên là số bộ test ~T~ ~(1 \le T \le 10^5)~.
• Mỗi bộ test gồm 1 dòng chứa hai số nguyên ~L~ và ~R~ cách nhau bởi một khoảng trắng
  ~(1 \le L \le R \le 10^{12})~.

Output

Với mỗi bộ test, in ra trên một dòng số lượng các số mà Jim thích nằm trong đoạn ~[L, R]~.

Sample

Problem

Đêm Giao Thừa, bạn có một dãy phong bao lì xì ~a~ gồm ~n~ phong bao, mỗi phong bao ghi một số nguyên không âm. Bạn cũng được cho một số nguyên ~k~.

Gọi ~f(l, r)~ là giá trị MEX của đoạn con ~(a_l, a_{l+1}, \dots, a_r)~*.

Bạn phải thực hiện đúng ~n - k + 1~ lần thao tác sau:

• Gọi độ dài hiện tại của dãy là ~|a|~. Hãy tìm một đoạn liên tiếp ~[l, r]~ có độ dài ~k~ sao cho: ~\max_{i=1}^{|a|-k+1} f(i, i+k-1) = f(l, r).~

  Nói cách khác, trong tất cả các cửa sổ độ dài ~k~, bạn phải chọn một cửa sổ có MEX lớn nhất. Nếu có nhiều đoạn ~[l, r]~ cùng đạt cực đại, bạn có thể chọn bất kỳ đoạn nào.

• Sau khi đã chọn ~[l, r]~, bạn được chọn bất kỳ chỉ số ~i~ thỏa ~l \le i \le r~ và xóa phần tử ~a_i~ khỏi dãy ~a~. Khi đó dãy mới trở thành:

  ~[a_1, a_2, \dots, a_{i-1}, a_{i+1}, a_{i+2}, \dots, a_{n}]~.

Ví dụ minh họa: Với dãy ~[1, 2, 0, 1, 3, 0]~ và ~k = 3~, có hai cặp ~(l, r)~ có thể được chọn là ~(1, 3)~ và ~(2, 4)~ (vì cả hai đoạn này đều có ~mex = 3~, là lớn nhất trong mọi cửa sổ độ dài ~3~). Do đó, bạn có thể xóa bất kỳ chỉ số ~1, 2, 3, 4~ nào ở bước tiếp theo.

Sau khi thực hiện ~n - k + 1~ thao tác, dãy sẽ còn đúng ~k - 1~ phần tử. Mục tiêu của bạn là tối đa hóa MEX của dãy còn lại.

Hãy in ra giá trị MEX lớn nhất có thể đạt được.

* Chú thích (MEX): MEX (minimum excluded) của một tập các số nguyên ~c_1, c_2, \dots, c_m~ được định nghĩa là số nguyên không âm nhỏ nhất ~x~ không xuất hiện trong tập đó.

Input

Mỗi input gồm nhiều test.

• Dòng đầu chứa số nguyên ~t~ — số lượng test case ~(1 \le t \le 10^4)~.

• Với mỗi test case:

  • Dòng 1 chứa hai số nguyên dương ~n~ và ~k~ ~(2 \le k \le n \le 2 \cdot 10^5)~.
  • Dòng 2 chứa ~n~ số nguyên ~a_1, a_2, \dots, a_n~ ~(0 \le a_i \le n)~.

Bảo đảm rằng tổng ~n~ qua tất cả test case không vượt quá ~2 \cdot 10^5~.

Output

Với mỗi test case, in ra một số nguyên không âm

Sample

Note

• Ở test case đầu tiên, ta có thể chọn đoạn [1, 3]. Sau đó, xóa phần tử ~a_2~ để thu được dãy [0, 0]. Quá trình kết thúc và mex của các phần tử còn lại là 1.

• Ở test case thứ ba, ta có thể thực hiện các thao tác sau:

  • Chọn ~i = 1, j = 3~. Điều này hợp lệ vì mex của tất cả các cửa sổ độ dài 3 lần lượt là 3, 0, 3, và cửa sổ [1, 3] có mex = 3 (lớn nhất). Sau đó, xóa ~a_2~. Dãy lúc này là [0, 2, 1, 0].
  • Chọn ~i = 2, j = 4~. Sau đó, xóa ~a_2~. Dãy lúc này là [0, 1, 0].
  • Chọn ~i = 1, j = 3~. Sau đó, xóa ~a_1~. Dãy lúc này là [1, 0]. Quá trình kết thúc và mex cuối cùng là 2.

Problem

Mùng Một Tết đến, chị Alice lại bày ra một thử thách nho nhỏ cho anh Bob để nhận lì xì: đưa cho Bob hai dãy số ~a~ và ~b~, mỗi dãy có độ dài ~n~.

Điều đặc biệt là tất cả các số nguyên từ ~1~ đến ~2n~ xuất hiện đúng một lần trong một trong hai dãy ~a~ hoặc ~b~. Nói cách khác, khi ~ghép^*~ hai dãy lại thành ~a + b~ thì ta nhận được một hoán vị độ dài ~2n^†~.

Bob phải sắp xếp tăng dần cả hai dãy cùng lúc, nhưng chỉ được phép dùng đúng phép swap của Alice.

Phép đổi chỗ swap của Alice được mô tả như sau:

• Chọn hai chỉ số ~i~ và ~j~ với ~i \ne j~.
• Thực hiện đồng thời:
  • đổi chỗ ~a_i~ với ~b_j~,
  • và đổi chỗ ~b_i~ với ~a_j~.

Nhiệm vụ của bạn: với mỗi test, hãy xác định liệu Bob có thể làm cho cả hai dãy ~a~ và ~b~ đều tăng dần bằng cách áp dụng phép swap trên một số lần bất kỳ hay không.

Chú thích:
* Dãy ghép ~a + b~ được hiểu là ~[a_1, a_2, a_3, \ldots, a_n, b_1, b_2, b_3, \ldots, b_n]~.
~†~ Một hoán vị độ dài ~m~ là một dãy chứa đầy đủ các số nguyên từ ~1~ đến ~m~ theo một thứ tự nào đó.

Input

Dữ liệu gồm nhiều bộ test.

• Dòng đầu chứa số bộ test ~t~ ~(1 \le t \le 10^4)~.
• Với mỗi test:
  • Dòng 1 chứa số nguyên ~n~ ~(3 \le n \le 2 \cdot 10^5)~.
  • Dòng 2 chứa ~n~ số ~a_1, a_2, \ldots, a_n~ ~(1 \le a_i \le 2n)~.
  • Dòng 3 chứa ~n~ số ~b_1, b_2, \ldots, b_n~ ~(1 \le b_i \le 2n)~.

Bảo đảm rằng mọi số trong đoạn ~[1, 2n]~ xuất hiện đúng một lần trong hoặc ~a~ hoặc ~b~.

Output

Với mỗi test:

• In YES nếu có thể sắp xếp đồng thời cả hai dãy theo thứ tự tăng dần.
• Ngược lại, in NO.

Sample

Note

• Ở test đầu tiên, có thể thấy rằng việc sắp xếp đồng thời là không thể.
• Ở test thứ hai, Bob có thể thực hiện một phép đổi chỗ với hai chỉ số ~i = 1~ và ~j = 2~. Khi đó, hai dãy lần lượt trở thành ~[3, 4, 5]~ và ~[1, 2, 6]~. Lúc này, cả hai dãy đều đã được sắp xếp tăng dần.