ami rất thích những số \(0\), vì nó xấp xỉ bằng trình nói xạo của cuom1999. Biết được điều này, cuom1999 đã cho ami một số \(a\). Nhưng ngặt nghẽo thay, ami chỉ thích những số có ít nhất \(x\) số \(0\) tận cùng. Bây giờ, ami đang bận gánh cuom1999 lên Đại Cao Thủ, các bạn hãy tìm ra một số tự nhiên \(b\) NHỎ NHẤT mà \(a + b\) có ít nhất \(x\) số \(0\) tận cùng nhé.

Input

• 1 dòng 2 số nguyên không âm \(a\) và \(x\).

Output

• In ra một số \(b\) tương ứng.

Scoring

• Subtask \(1\) (\(20\%\) số điểm): \(a \leq 10^{15}, x \leq 7\)

• Subtask \(2\) (\(80\%\) số điểm): \(a \leq 10^{15}, x \leq 15\)

Example

10 2

90

Một lần, CJ, Catalina và FanXzitThamer, đàn em của CJ, đã cướp thành công một ngân hàng, với số tiền \(N\) nghìn đô la Mỹ. Sau khi cướp được, \(3\) người quyết định chia tiền như sau:

• Số tiền Catalina, CJ, FanXzitThamer lần lượt được chia là: \(x, y, z\) (nghìn đô la Mỹ) \((1 \leq x, y, z)\).
• \(x > y > z\).
• \(x + y + z = N\).

Và CJ muốn tính toán là có bao nhiêu cách chia như vậy. Vì CJ quên cầm máy tính nên các bạn hãy giúp CJ nhé.

Input

• Gồm duy nhất số nguyên dương \(N\).

Output

• Gồm một số duy nhất là kết quả tìm được.

Example

9 

3

Một ngày, khi học sinh lớp \(1\) đang học về số học, giáo sư Wu Zi Mu đã ra bài tập như sau:

“Định nghĩa \(F(N)\) là số ước nguyên dương của \(N\). Ví dụ: \(F(12)=6,F(5)=2\).

Cho \(Q\) truy vấn, mỗi truy vấn chứa hai số \(A,B\). Nhiệm vụ là đếm tất cả số \(X\) nằm trong khoảng [A,B] mà \(F(X)\) là số nguyên tố lớn hơn \(2\).”

Học sinh lớp \(1\) đang cố tìm cách để giải bài này, nhưng không tìm ra được. Các bạn hãy giúp cho các học sinh đó nhé.

Input

• Gồm \(Q+1\) dòng:
• Dòng đầu tiên gồm số \(Q\) là số truy vấn.
• \(Q\) dòng tiếp theo, mỗi dòng chứa 2 số nguyên \(A,B\).

Output

• Gồm \(Q\) dòng là kết quả của \(Q\) truy vấn .

Constraints

• \(1 \leq A,B \leq 10^{12}\)
• \(1 \leq Q \leq 10^{5}\)

Scoring

• Subtask \(1\) (\(30\%\) số điểm): \(1 \leq A,B \leq 10^{3}, Q \leq 10^3\).
• Subtask \(2\) (\(30\%\) số điểm): \(1 \leq A,B \leq 10^{6}, Q \leq 10^5\).
• Subtask \(3\) (\(40\%\) số điểm): Không có ràng buộc gì thêm.

Example

2
3 25
1 100 

4
7

Nhà nghiên cứu sinh học, Zero đã bắt tay vào công việc nghiên cứu GEN thuần chủng.

GEN là một đoạn kết gắn các cặp ADN, mỗi cặp ADN được đặc trưng bằng một chữ cái trong tập \({A, T, X, G}\). GEN thuần chủng là là GEN hình thành từ một đoạn ADN cơ sở, được gắn kết lặp đi lặp lại nhiều lần và ở lần lặp cuối cùng có thể chỉ chứa phấn đầu của đoạn cơ sở. GEN được mô tả dưới dạng xâu \(S\) chỉ chứa các ký tự trong tập nêu trên. Như vậy GEN thuần chủng là xâu có thể biểu diễn như tổng của \(k\) đoạn cơ sở (\(k \leq 0)\) và có thể có thêm một đoạn đầu của cơ sở.

Ví dụ với \(S\) = AXATAGAXATAGAXATAGAXA là một GEN thuần chủng vì có đoạn cơ sở là AXATAG và \(S\) = AXATAG + AXATAG + AXATAG + AXA. Cho GEN \(S\) độ dài \(n\). Đưa ra đoạn cơ sở ngắn nhất của xâu \(S\).

Input

• Gồm một dòng duy nhất chứa xâu \(S\) chỉ chứa các ký tự in hoa \({A, T, X, G}\)

Output

• Gồm đoạn cơ sở ngắn nhất của xâu \(S\).

Constraints

• \(S.size() \leq 5.10^{6}\)

Scoring

• Subtask \(1\) (\(50\%\) số điểm): \(S.size() \leq 5.10^3\).
• Subtask \(2\) (\(50\%\) số điểm): Không có ràng buộc gì thêm.

Example

AXATAGAXATAGAXATAGAXA 

AXATAG

Giáo sư Wu Zi Mu đã tiếp tục ra bài tập cho học sinh lớp \(1\) như sau:

"Định nghĩa \(S(N)\) là tổng tất cả các ước nguyên dương của \(N\). Ví dụ: \(S(12)=1+2+3+4+6+12=28\)

Cho \(Q\) truy vấn, mỗi truy vấn gồm số nguyên dương \(N\). Tính \(S(N!^{3})\) mod \(1200000090\)"

Học sinh nghĩ mãi không ra. Các bạn hãy giúp học sinh trả lời \(Q\) truy vấn trên.

Input

• Gồm \(Q+1\) dòng:
• Dòng đầu tiên gồm số \(Q\).
• \(Q\) dòng tiếp theo, mỗi dòng chứa số nguyên dương \(N\).

Output

• Gồm \(Q\) dòng là kết quả của \(Q\) truy vấn theo thứ tự từ trên xuống dưới, in ra từng dòng.

Constraints

• \(1 \leq N \leq 4.10^{7}\)
• \(1 \leq Q \leq 10\)

Scoring

• Subtask \(1\) (\(10\%\) số điểm): \(N \leq 5, Q \leq 3\).
• Subtask \(2\) (\(30\%\) số điểm): \(N \leq 10^{4}, Q \leq 10\).
• Subtask #3 (\(30\%\) số điểm): \(N \leq 10^{6}, Q \leq 10\).
• Subtask #4 (\(30\%\) số điểm): \(N \leq 4.10^{7}, Q \leq 4\), tổng các \(N\) trong \(Q\) truy vấn không quá \(4.10^{7}\).

Example

2
4 
3  

40920
600