Bài tập

Gọi \(T = N! = 1 \times 2 \times \dots \times N\). Một số nguyên dương \(x\) được gọi là "đặc biệt" nếu \(x\) là ước của \(T\) và \(x\) có đúng \(75\) ước dương.

Cho \(N\), hãy đếm xem có bao nhiêu số đặc biệt.

Input

• Một dòng duy nhất chứa số nguyên dương \(N\).

Output

• In ra số lượng số đặc biệt.

Constraints

• Có 30% số test với \(1 \le N \le 15\).
• Có 30% số test với \(1 \le N \le 28\).
• Có 20% số test với \(1 \le N \le 78\).
• Có 20% số test với \(1 \le N \le 200\).

Sample Input

14

Sample Output

2

Explanation

Số \(14!\) có đúng hai ước có \(75\) ước dương. Chẳng hạn \(2^4 \cdot 3^4 \cdot 5^2\) có \(5\cdot5\cdot3 = 75\) ước.

Bà Bảy viết lên bảng dãy số tự nhiên bắt đầu từ \(1\), nhưng bỏ qua mọi số chia hết cho \(7\) hoặc có chữ số hàng đơn vị bằng \(7\). Dãy trên bảng là

(các số \(7, 14, 17, 21, \dots\) bị bỏ qua).

Với mỗi câu hỏi cho số nguyên \(N\), hãy cho biết số ở vị trí thứ \(N\) trong dãy.

Input

• Dòng đầu chứa số nguyên \(T\) là số câu hỏi.
• \(T\) dòng tiếp theo, mỗi dòng chứa một số nguyên \(N\).

Output

In ra \(T\) dòng, dòng thứ \(i\) là đáp án của câu hỏi thứ \(i\).

Constraints

• \(1 \le T \le 10^5\).
• \(1 \le N \le 10^{18}\).

Sample Input

3
7
13
15

Sample Output

8
15
18

Một xưởng có \(N\) cuộn dây điện, cuộn thứ \(i\) dài \(a_i\) mét. Người thợ cần cắt các cuộn này để thu được ít nhất \(K\) đoạn dây có cùng độ dài nguyên \(L\) (mỗi đoạn phải nằm gọn trong một cuộn; không cần dùng hết dây, phần thừa được bỏ đi).

Hãy tìm giá trị \(L\) lớn nhất có thể. Nếu không tồn tại \(L \ge 1\) nào thoả mãn thì in ra \(0\).

Input

• Dòng đầu chứa hai số nguyên \(N\) và \(K\).
• Dòng thứ hai chứa \(N\) số nguyên \(a_1, \dots, a_N\).

Output

In ra một số nguyên là độ dài lớn nhất tìm được (hoặc \(0\) nếu không thể).

Constraints

• \(1 \le N \le 10^5\).
• \(1 \le K, a_i \le 10^9\).

Sample Input

3 7
25 17 9

Sample Output

6

Explanation

Với \(L = 6\): \(\lfloor 25/6 \rfloor + \lfloor 17/6 \rfloor + \lfloor 9/6 \rfloor = 4 + 2 + 1 = 7\) đoạn. Với \(L = 7\) chỉ được \(3+2+1 = 6\) đoạn, không đủ.

Ta gọi một dãy số nguyên dương \(b_1, b_2, \dots, b_k\) là dãy chia hết nếu \(b_k \le n\) và mỗi phần tử là ước của phần tử đứng ngay sau nó, tức là \(b_i \mid b_{i+1}\) với mọi \(1 \le i < k\). (Do ước không vượt quá bội nên dãy này cũng thoả \(b_1 \le b_2 \le \dots \le b_k \le n\); các phần tử có thể bằng nhau.)

Cho hai số nguyên \(n\) và \(k\). Hãy đếm số dãy chia hết có độ dài đúng \(k\). Vì kết quả có thể rất lớn, in ra phần dư khi chia cho \(10^9 + 7\).

Input

Một dòng chứa hai số nguyên \(n\) và \(k\).

Output

In ra một số nguyên là số dãy chia hết độ dài \(k\), lấy modulo \(10^9 + 7\).

Constraints

• \(1 \le n, k \le 2000\)

Sample Input

6 3

Sample Output

25

Explanation

Với \(n = 6\), \(k = 3\) có \(25\) dãy thoả mãn, chẳng hạn \((1,1,1)\), \((1,2,6)\), \((2,4,4)\), \((3,3,6)\), \((6,6,6)\), ...