Trong số học, số phong phú là các số mà tổng các ước số của số đó, không kể chính nó, lớn hơn số đó.

Ví dụ, số \(12\) có tổng các ước số không kể \(12\) là:

Do đó, \(12\) là một số phong phú.

Bạn hãy lập trình đếm xem có bao nhiêu số phong phú trong đoạn \([L, R]\).

Input

Gồm hai số nguyên \(L\) và \(R\):

Output

In ra một số nguyên duy nhất là số lượng số phong phú trong đoạn \([L, R]\).

Giới hạn

• Có \(50\%\) số test thỏa mãn:

Sample Input

1 50

Sample Output

9

Ghi chú

Từ \(1\) đến \(50\) có \(9\) số phong phú là:

Bạn được cho \(n\) số nguyên. Với mỗi số nguyên, nhiệm vụ của bạn là xác định số lượng ước số của nó.

Ví dụ, nếu \(x = 18\), đáp án là \(6\) vì các ước số của \(18\) là:

Dữ liệu vào

Dòng đầu tiên chứa số nguyên \(n\): số lượng số nguyên cần xử lý.

Trong \(n\) dòng tiếp theo, mỗi dòng chứa một số nguyên \(x\).

Dữ liệu ra

Với mỗi số nguyên \(x\), in ra số lượng ước số của nó trên một dòng riêng.

Ràng buộc

• \(1 \le n \le 10^5\)
• \(1 \le x \le 10^6\)

Ví dụ

Input

3
16
17
18

Output

5
2
6

Trong một liên hoan phim, có \(n\) bộ phim sẽ được trình chiếu.

Bạn biết thời gian bắt đầu và thời gian kết thúc của mỗi bộ phim.

Hãy xác định số lượng phim lớn nhất mà bạn có thể xem trọn vẹn.

Dữ liệu vào

Dòng đầu tiên chứa số nguyên \(n\): số lượng bộ phim.

Trong \(n\) dòng tiếp theo, mỗi dòng chứa hai số nguyên \(a\) và \(b\): thời gian bắt đầu và thời gian kết thúc của một bộ phim.

Dữ liệu ra

In ra một số nguyên duy nhất: số lượng phim lớn nhất có thể xem trọn vẹn.

Ràng buộc

• \(1 \le n \le 2 \cdot 10^5\)
• \(1 \le a < b \le 10^9\)

Ví dụ

Input

3
3 5
4 9
5 8

Output

2

Có \(n\) trẻ em muốn đi vòng quay khổng lồ. Nhiệm vụ của bạn là sắp xếp cabin cho mỗi trẻ.

Mỗi cabin có thể chứa một hoặc hai trẻ em. Ngoài ra, tổng cân nặng của những trẻ em trong một cabin không được vượt quá \(x\).

Bạn biết cân nặng của từng trẻ em.

Hãy xác định số cabin ít nhất cần sử dụng.

Dữ liệu vào

Dòng đầu tiên chứa hai số nguyên \(n\) và \(x\): số lượng trẻ em và tổng cân nặng tối đa mà một cabin có thể chứa.

Dòng tiếp theo chứa \(n\) số nguyên:

Trong đó \(p_i\) là cân nặng của trẻ em thứ \(i\).

Dữ liệu ra

In ra một số nguyên duy nhất: số cabin ít nhất cần sử dụng.

Ràng buộc

• \(1 \le n \le 2 \cdot 10^5\)
• \(1 \le x \le 10^9\)
• \(1 \le p_i \le x\)

Ví dụ

Input

4 10
7 2 3 9

Output

3