Jump20 Children Div 1

Tối đến, nhân trời trăng thanh gió mát, nhìn lên trời, \(Kaninho\) bỗng nảy ra một bài toán hay và muốn đố các bạn như sau:

• Cho hai dãy số nguyên dương gồm \(n\) phần tử \(a_1,a_2,...,a_n\) và \(b_1,b_2,...,b_n\).

Đặt \(M=a_1^{b_1}a_2^{b_2}...a_n^{b_n}\)

Yêu cầu: Tìm số nguyên dương \(x\) nhỏ nhất sao cho \(x!\) chia hết cho \(M\).

Input

• Dòng thứ nhất chứa số \(t\) \((1\le t\le 50)\) - Thể hiện số testcase

• \(t\) test tiếp theo, mỗi test có dạng như sau:

  • Dòng đầu tiên chứa số \(n(1\le n\le 100)\)

  • \(n\) dòng tiếp theo, mỗi dòng chứa hai số nguyên \(a_i\), \(b_i\) \((1\le a_i\le 100,1\le b_i\le 10^{13})\)

Output

• Ứng với mỗi testcase, in ra đáp án cần tìm

Scoring

• Subtask \(1\) (\(37.5\%\) số điểm): \(1\le n\le 10 ; 1\le a_i\le 10; 1 \le b_i \le 5\)

• Subtask \(2\) (\(62.5\%\) số điểm): không có ràng buộc nào thêm.

Example

1
2
3 2
4 1

6

Sáng hôm nay, \(Kaninho\) được cô giáo khen vì đã làm được một bài toán hóc búa và để chia sẻ niềm vui này cho nhiều người, cậu ấy quyết định đăng bài toán này lên đây để mọi người cùng thử sức. Bài toán có đề bài như sau:

• Kí hiệu \(u(n)\) là số nguyên nhỏ nhất có tổng các chữ số bằng \(n\).

• Kí hiệu \(g(k)=\sum\limits_{n=1}^{k}u(n)\).

Gọi \(f_i\) là phần tử thứ \(i\) của dãy fibonacci, trong đó: \(f_0=0,f_1=1\) và \(f_{i}=f_{i-2}+f_{i-1}\) với mọi \(i\ge 2\)

Yêu cầu: Tính \(z(q)=\sum\limits_{i=2}^{q}g(f_i)\) với số \(q\) nguyên dương cho trước. Vì đáp án có thể lớn, nên ta cần mod \(10^9+7\) trước khi in ra.

Input

• Dòng thứ nhất chứa số \(t(1\le t\le 50)\) - Thể hiện số lượng testcase của bài toán

• \(t\) dòng tiếp theo, mỗi dòng chứa số nguyên dương \(q(2\le q\le 90)\)

Output

• Ứng với mỗi testcase, in ra đáp án cần tìm

Scoring

• Subtask \(1\) (\(37,5\%\) số điểm): \(2\le q\le 10\)

• Subtask \(2\) (\(62,5\%\) số điểm): Không có điều kiện gì

Example

2
2
3

1
4

Hôm qua là bữa kiểm tra kiến thức tổng hợp để chuẩn bị đi thi HSG, vì nhận thấy \(Kaninho\) còn yếu về phần mảng, nên hôm nay bố của \(Kaninho\) quyết định ra một bài toán nhằm củng cố kiến thức cho Kaninho như sau:

Cho mảng \(a\) gồm \(n\) phần tử, và chỉ số của mảng bắt đầu từ \(1\).

Yêu cầu: Với mỗi phần tử \(i\) \((1\le i\le n)\) tìm phần tử \(a[j]\) thoả mãn:

• \(1\) < \(i\) < \(j\le n\)

• \(a[i]\) < \(a[j]\)

• \(j\) - \(i\) là nhỏ nhất.

Nếu không tồn tại \(a[j]\) thoả mãn in ra \(-1\)

Input

• Dòng thứ nhất chứa số \(t\) \((1\le t\le 10)\) - Thể hiện số lượng testcase

• \(t\) test tiếp theo, mỗi test có dạng như sau:

• Dòng thứ nhất chứa số \(n\) \((1\le n\le 10^5)\)

• Dòng thứ hai chứa \(n\) số nguyên \(a_i\) \((1\le a_i\le 50)\)

Output

• Ứng với mỗi testcase, in ra đáp án cần tìm

Scoring

• Subtask \(1\) (\(37.5\%\) số điểm): \(1\le n\le 20\).

• Subtask \(2\) (\(62.5\%\) số điểm): không có điều kiện gì thêm.

Example

2
5
2 3 1 9 4
7
5 7 9 3 2 1 4

3 9 9 -1 -1 
7 9 -1 4 4 4 -1 

\(Kaninho\) được cho một xâu \(S\) chỉ gồm các kí tự latin thường, và nhiệm vụ của anh ấy là đếm xem có bao nhiêu xâu con (gồm những phần tử liên tiếp) thoả mãn số lần xuất hiện của mỗi kí tự trong xâu con đó không lớn hơn \(K\)

Input

• Dòng thứ nhất chứa số \(t(1\le t\le 100)\) - Thể hiện số testcase

• \(t\) test tiếp theo, mỗi dòng chứa một test có dạng như sau:

• Dòng thứ nhất chứa xâu \(S\) - Biết rằng, độ dài xâu \(S\) không vượt quá \(10^5\)

• Dòng thứ hai chứa số \(K\) \((1\le K\le 10^5)\)

Output

• Ứng với mỗi testcase, in ra đáp án cần tìm

Scoring

• Subtask \(1\) (\(37.5\%\) số điểm): \(1\) \(\le\) |S| \(\le 20\) ,\(1\) \(\le\) \(K\) \(\le 5\).

• Subtask \(2\) (\(62.5\%\) số điểm): không có điều kiện gì thêm.

Example

1
abc
1

6

Hôm nay, được dịp nghỉ lễ nên bố Kaninho dắt Kaninho ra vườn và đố anh ta một bài toán như sau:

Có \(n\) cái cây được sắp xếp trên trục toạ độ \(Ox\) có toạ độ lần lượt là : \(X_1,X_2,...,X_n\) và chiều cao tương ứng lần lượt là: \(H_1,H_2,...,H_n\)

• "Độ chênh lệch xa" của \(2\) cái cây bất kì được xác định như sau:

• Đầu tiên ta sẽ sắp xếp lại tất cả các cái cây theo tứ tự tăng dần theo toạ độ . Cây có toạ độ nhỏ nhất sẽ có thứ tự là \(1\). Những cây nào có cùng toạ độ thì sẽ cùng thứ tự. Ví dụ, ta có \(5\) cái cây có toạ độ lần lượt là \(3,3,1,3,4\) thì thứ tự của chúng sẽ lần lượt là: \(2,2,1,2,5\).

• Khi đó "độ chênh lệch xa" của hai cái cây thứ \(i\) và thứ \(j\) bất kì sẽ là \(|D_i-D_j|\) - Trong đó: \(D_i,D_j\) là thứ tự của hai cây thứ i và \(j\) sau khi đã được sắp xếp.

• Tiếp theo: "Độ chênh lệch cao" của \(2\) cái cây bất kì được xác định như sau:

• Đầu tiên ta sẽ sắp xếp lại tất cả các cái cây theo tứ tự tăng dần theo chiều cao . Cây có chiều cao nhỏ nhất sẽ có thứ tự là \(1\). Những cây nào có cùng chiều cao thì sẽ cùng thứ tự. Ví dụ, ta có \(5\) cái cây có chiều cao lần lượt là \(4,1,9,7,4\) thì thứ tự của chúng sẽ lần lượt là: \(2,1,5,4,2\).

• Khi đó "độ chênh lệch cao" của hai cái cây thứ \(i\) và thứ \(j\) bất kì sẽ là \(min(E_i,E_j)\) - Trong đó: \(E_i,E_j\) là thứ tự của hai cây thứ \(i\) và \(j\) sau khi đã được sắp xếp.

• Cuối cùng "độ tương thích" của hai cái cây bất kì chính bằng tích của "độ chênh lệch xa" và "độ chênh lệch cao" của hai cây đó

Yêu cầu: Tính tổng "độ tương thích" của tất cả các cặp cây trên.

Input

• Đề bài sẽ có nhiều testcase, mỗi test có dạng như sau:

• Dòng thứ nhất chứa số \(n\) \((2\le n\le 10^5)\) - Thể hiện số lượng cây.

• \(n\) dòng tiếp theo, mỗi dòng chứa hai số nguyên \(X_i\), \(H_i\) (\(0 <\) \(X_i\), \(H_i\) \(\le\) \(10^9\)) - Thể hiện toạ độ và chiều cao của cây thứ \(i\)

Output

• Ứng với mỗi testcase, in ra đáp án cần tìm

Scoring

• Subtask \(1\) (\(37.5\%\) số điểm): \(1\le n \le 20\) ; \(0<X_i,H_i\le 50\).

• Subtask \(1\) (\(62.5\%\) số điểm): không có điều kiện gì thêm.

Example

2
3 4
4 5
3
7 8
9 8
6 5

1
5

Hôm nay nhân ngày đẹp trời, \(Kaninho\) quyết định lên mạng để học về những bài toán IQ, vô tình anh ta đọc được bài toán như sau :

Gọi \(A\) là tập hợp tất cả các số nguyên dương không lớn hơn \(n\). \(Henry\) muốn chọn một vài số từ tập đó và chúng thoả mãn \(2\) điều kiện sau:

• Số lượng các số được chọn ít nhất là \(1\) và nhiều nhất là \(k\)

• Không tồn tại số chính phương \(f(f\ne 1)\) nào thoả mãn \(f\) là ước của tích các số được chọn.

Yêu cầu: Hãy đếm xem \(Henry\) có bao nhiêu cách chọn các số như vậy.

Vì chưa có kinh nghiệm nhiều trong những bài toán như vậy, nên \(Kaninho\) quyết định lên đây để nhờ các bạn giúp đỡ. Là một lập trình viên tài năng, hãy giúp anh ấy một tay nhé !

Input

• Dòng thứ nhất chứa số \(t\) (1 \(\le\) \(t\) \(\le\) 5) - thể hiện số testcase

• \(t\) dòng tiếp theo, mỗi dòng chứa hai số nguyên dương \(n\), \(k\) (1 \(\le\) \(n\), \(k\) \(\le\) 500)

Output

• Ứng với mỗi testcase, in ra đáp án cần tìm sau khi đã mod \(10^9+7\).

Scoring

• Subtask \(1\) (\(37.5\%\) số điểm): \(1\le n,k\le 20\).

• Subtask \(2\) (\(62.5\%\) số điểm): không có điều kiện gì thêm.

Example

2
2 2
3 2

3
6