Problem E: 儿童节发礼物

Problem E: 儿童节发礼物

Time Limit: 1 Sec  Memory Limit: 128 MB
Submit: 63  Solved: 11
[Submit] [Status] [Web Board] [Creator:]

Description

zser喜欢素数,现在他有一个操作:从一个区间中选两个以上的数相乘。

如果相乘得到的数是素数,zser就会在儿童节多送一个礼物。

一开始zser不准备在儿童节送礼物,但之后zser会选择N个区间,在这每个区间他会进行最多K次操作,当然这K次操作不会存在重复。

请问zser最多会送多少个儿童节礼物?

Input

第一行输入两个数N和K。(1≤N≤106,1≤K≤109)

接下来N行,每行输入两个整数L和R表示zser进行操作的区间 [L,R]。(1≤L≤R≤106)

Output

输出一个整数表示zser最多会送多少个儿童节礼物

Sample Input Copy

2 5
2 10
1000 5000

Sample Output Copy

0