Bài tập

Cho dãy số \(A\) gồm \(n\) phần tử nguyên dương \(A_1,A_2,…,A_n\). Hãy loại một phần tử bất kỳ trong dãy số và đặt \(P\) tích các số còn lại. Phân tích thừa số nguyên tố của \(P\), sau đó tính tổng các số mũ trong thừa số nguyên tố đó. Hãy tìm cách bỏ loại bỏ số nào để tổng các số mũ nhỏ nhất có thể.

Ví dụ: cho dãy số gồm \(4\) số \(1; 2; 4; 10\). có 2 cách bỏ đều cho tổng số mũ bằng \(3\) là nhỏ nhất:

• Cách 1: Loại bỏ số \(4\), ta có \(P=1 * 2*10=20=2^2*5\) có tổng số mũ bẳng \(3\)

• Cách 2: Loại bỏ số \(10,\) ta có \(P=1 * 2*4=8=2^3\) có tổng số mũ bẳng \(3\)

Yêu cầu: Cho dãy số \(A\), hãy in ra tổng số mũ nhỏ nhất của phân tích thừa số sau khi bỏ một phần tử.

Input

• Dòng đầu tiên chứa dãy số \(n (n≤10^5)\).

• Dòng thứ 2 chứa \(n\) phần tử của dãy số \(A (A_i≤10^6)\).

Output

Một số nguyên là tổng số mũ nhỏ nhất của phân tích thừa số sau khi bỏ một phần tử.

Example

4
1 2 4 10

3

Scoring

• Subtask \(1\) (\(30\%\) số điểm): \(N≤10^4\) và \(A_i≤3\).

• Subtask \(2\) (\(30\%\) số điểm): \(N≤10^4\) và \(A_i≤8\).

• Subtask \(3\) (\(30\%\) số điểm): \(N≤10^4\) và \(A_i≤10^6\).

• Subtask \(4\) (\(10\%\) số điểm): trường hợp còn lại.

Xét dãy vô hạn các số tự nhiên liên tiếp bắt đầu từ \(1\): \(1, 2, 3,...\) và \(n\) số nguyên dương \(a_{1}, a_{2}, ..., a_{n}\). Trên dãy vô hạn các số tự nhiên này, tiến hành xóa hết các số chia hết cho \(a_{1}\), sau đó xóa hết các số chia hết cho \(a_{2}\) mà chưa được xóa,..., cuối cùng xóa hết các số chia hết cho \(a_{n}\) mà chưa được xóa. Đánh số các số chưa được xóa bắt đầu từ \(1\), người ta muốn biết số được đánh số thứ \(k\) là số nào?

Yêu cầu: Cho dãy số \(a_{1}, a_{2}, ..., a_{n}\) và \(k\), hãy tìm số tự nhiên được đánh số thứ \(k\) trên dãy sau khi xóa.

Input

--- Dòng đầu chứa số nguyên \(T\) là số bộ dữ liệu;

--- \(T\) nhóm dòng sau, mỗi nhóm có dạng:

o Dòng đầu của nhóm chứa hai số nguyên dương \(n\) và \(k\) \((1 ≤ k ≤ 10^{15})\);

o Dòng thứ hai của nhóm chứa \(n\) số nguyên dương \(a_{1}, a_{2}, ..., a_{n}\) \((1 < a_{i} ≤ 10^{15})\).

Output

• Gồm \(T\) dòng, mỗi dòng chứa một số tự nhiên là kết quả tương ứng của bộ test trong dữ liệu vào.

Example

1
2 5
3 4

10

Scoring

\(30\%\) số test có \(n = 1\)

\(30\%\) số test có \(n = 2\)

\(40\%\) số test có \(n \leq 10\)

Những ngọn nến lung linh huyền ảo khiến biết bao người đam mê, trong số đó có Nhan_Tai. Một hôm, Tai_Nhan đưa cho anh \(n\) cây nến với độ cao đôi một khác nhau. Theo đó, Nhan_Tai sẽ phải xếp \(n\) cây nến này theo một đường thẳng sao cho các cây nến ở vị trí chẵn thì cao hơn hai cây nến hai bên (nếu có), và dĩ nhiên, các cây nến ở vị trí lẻ thì thấp hơp hai cây nến hai bên (nếu có). Cụ thể, cách xếp phải thỏa mãn với mọi \(1 ≤ i ≤ n\):

• Nếu \(i\) chẵn: \(i > 1\) ⇒ \(h_{i−1} < h_{i}\); \(i < n\) ⇒ \(h_{i+1} < h_{i}\)

• Nếu \(i\) lẻ: \(i > 1\) ⇒ \(h_{i−1} > h_{i}\) ; \(i < n\) ⇒ \(h_{i+1} > h_{i}\)

Ở đây \(h_{i}\) được hiểu như là độ cao của cây nến xếp ở vị trí thứ \(i\) trên đường thẳng. Anh ta muốn biết mình có bao nhiêu cách khác nhau để xếp các cây nến. Vốn nhìn xa trông rộng, Nhan_Tai biết sẽ có thể có rất nhiều cách xếp, anh ta chỉ yêu cầu in ra \(9\) chữ số tận cùng của số cách xếp

Input

• Dòng đầu chứa \(2\) số nguyên \(Q\) là số lượng testcase

• Mỗi testcase nằm trên một dòng chứa đúng một số nguyên dương: \(n\)

Output

Gồm \(Q\) dòng trả lời cho \(Q\) testcase

Example

5
6
7
8
9
10

000000061
000000272
000001385
000007936
000050521

Scoring

• \(N, Q ≤ 5000\)

• Có \(50\%\) số test với \(n ≤ 100\)

Hôm nay là ngày đầu tiên đi học của Sơn, ở trường cô giáo dạy cho Sơn về các phép toán cộng trừ giữa các con số. Một kiến thức mới khiến Sơn cảm thấy rất hào hứng đó là phép toán tính khoảng cách hai số. Khoảng cách 2 số được xác định bằng tổng chênh lệch giữa các chữ số tương ứng của 2 số đó. Nếu 1 số có số lượng chữ số ít hơn số còn lại thì ta xem như thêm các số 0 ở phía trước.

Ví dụ:

• Khoảng cách hai số 4561 và 3278 bằng \(|4-3|+|5-2|+|6-7|+|1-8|=12\).

• Khoảng cách hai số 32 và 5678 bằng \(|0-5|+|0-6|+|3-7|+|2-8|=21\).

Bố của Sơn muốn kiểm tra xem con mình có khả năng tính toán siêu cấp hay không nên đã đưa ra một vấn đề liên quan đến phép toán khoảng cách hai số. Cho hai số nguyên dương \(L,R\) hãy tính tổng khoảng cách của tất cả cặp số \((A,B)\) thỏa mãn \(L\leq A\neq B\leq R\). Tuy là một người ra đề bài nhưng bố Sơn cũng không biết kết quả là bao nhiêu, vì vậy nhờ bạn hãy tính toán kết quả chia lấy dư cho \(10^9+7\) của bài toán trên và gửi lại cho bố Sơn.

Input

• Một dòng duy nhất gồm \(2\) số nguyên dương \(L,R\) (\(L\leq R\leq 10^{50000}\)).

Output

• In ra số nguyên là kết quả bài toán chia lấy dư cho \(10^9+7\).

Example

288 291

76

Scoring

• Subtask 1 (\(25\%\)): \(L,R\leq 10000\).

• Subtask 2 (\(30\%\)): \(L,R\leq 10^{100}\).

• Subtask 3 (\(45\%\)): Không có giới hạn gì thêm.