4063: 灯的开关状态
Memory Limit：128 MB
Time Limit：1 S
Judge Style：Text Compare
Creator：
Submit：55
Solved：28
Description
【问题描述】
有N盏灯放在一排，从1到N依次顺序编号，初始状态全部灯都是亮的。有N 个人也从1到N依次编号。1号将灯全部关闭，2号将凡是2的倍数的灯打开；3号将凡是3的倍数的灯作相反处理(该灯如为打开的，则将它关闭；如关闭的，则将它打开)。以后的人都和3号一样，将凡是自己编号倍数的灯作相反处理。
现在，第N个人操作后，输入M个询问，每个询问两个数S,E，输出从S到E之间（包含S,E）有多少盏灯是亮的。
【输入格式】b.in
第一行两个正整数N，M(1≤N,M≤2000000)。
接下来M行，每行两个正整数S,E（S≤E≤N）。
【输出格式】b.out
M行，每行一个正整数，表示从S到E之间（包含S,E）有多少盏灯是亮的。
【输入样例】
9 2
1 3
5 9
【输出样例】
2
4