Sinulle annetaan joukko lukuvälejä ja tehtäväsi on määrittää jokaisesta, monessako välin kokonaisluvussa jokainen numero on 0 tai 1.

Syöte

Ensimmäisellä rivillä on yksi kokonaisluku n: lukuvälien määrä.

Tämän jälkeen syötteessä on n riviä, joista kullakin on kaksi kokonaislukua a ja b: tutkittavana on lukuväli [a,b].

Tuloste

Tulosta jokaisen kyselyn vastaus omalle rivilleen.

Esimerkki

Syöte:

4
0 10
1 5
3 4
11 11

Tuloste:

3
1
0
1

Selitys: Esimerkiksi välillä [0,10] on kolme halutunlaista lukua: 0, 1 ja 10.

Osatehtävä 1 (12 pistettä)

• 1 \leq n \leq 1000
• 0 \leq a \leq b \leq 1000

Osatehtävä 2 (24 pistettä)

• 1 \leq n \leq 10^5
• 0 \leq a \leq b \leq 10^5

Osatehtävä 3 (64 pistettä)

• 1 \leq n \leq 10^5
• 0 \leq a \leq b \leq 10^{18}