Bài tập

Ba số nguyên dương \((A, B, C)\) được gọi là một bộ ba đẹp của \(N\) nếu \(A \times B + C = N\). Hai bộ khác nhau về thứ tự các thành phần được tính là khác nhau. Ví dụ với \(N = 4\) có \(5\) bộ ba đẹp: \((1,1,3)\), \((1,2,2)\), \((1,3,1)\), \((2,1,2)\), \((3,1,1)\).

Cho \(N\), hãy đếm số bộ ba đẹp.

Input

• Một số nguyên dương \(N\).

Output

• In ra số lượng bộ ba đẹp.

Constraints

• \(1 \le N \le 10^6\)

Sample Input

6

Sample Output

10

Explanation

Với \(C = 1\): \(A \times B = 5\) có 2 cách. \(C = 2\): tích bằng 4 có 3 cách. \(C = 3\): tích bằng 3 có 2 cách. \(C = 4\): tích bằng 2 có 2 cách. \(C = 5\): tích bằng 1 có 1 cách. Tổng cộng \(2+3+2+2+1 = 10\).

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 đủ.