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}$