Orice număr natural mai mare decât 2 poate fi scris ca sumă de numere naturale nenule aflate în ordine strict crescătoare, astfel încât orice termen al sumei, cu excepția primului termen, este un multiplu al termenului precedent din sumă. De exemplu, 27=3+6+18, unde 6 este multiplul lui 3, iar 18 este multiplul lui 6. Cum se dorește o descompunere formată dintr-un număr cât mai mare de termeni, vom obține și descompuneri cu 4 termeni: 27=1+2+8+16, 27=1+2+4+20, 27=1+2+6+18. Dintre cele trei descompuneri cu 4 termeni, descompunerea 27=1+2+4+20 este minimă din punct de vedere lexicografic (1 și 2 sunt la fel în cele trei descompuneri, dar 4 < 6 și 4 < 8). Numărul 30 poate fi descompus 30=2+4+8+16. El are o descompunere tot de lungime 4, dar este mai mare din punct de vedere lexicografic decât oricare dintre descompunerile cu patru termeni ale lui 27 (2 > 1).

Cerința

Pentru mai multe seturi de date formate din câte două numere naturale A și B, A ≤ B, se cere să se determine, pentru fiecare set una dintre următoarele cerințe:
1. numărul maxim de termeni în care pot fi descompuse numerele din intervalul [A,B] după regula descrisă în enunț;
2. numărul de numere din intervalul [A,B] care pot fi descompuse cu un număr maxim de termeni;
3. numărul din intervalul [A,B] care admite o descompunere cu un număr maxim de termeni, minimă din punct de vedere lexicografic.

Date de intrare

Din fișierul de intrare multisum.in se citesc, de pe prima linie, două numere N și C, despărțite printr-un spațiu, reprezentând numărul de seturi de date și tipul cerinței: C = 1 pentru cerința 1, C = 2 pentru cerința 2 și C = 3 pentru cerința 3. De pe următoarele N linii ale fișierului se citește câte o pereche de numere A și B, separate printr-un spațiu.

Date de ieșire

În fișierul de ieșire multisum.out se va scrie câte o linie pentru fiecare pereche A B din fișierul de intrare, linie care va conține numărul cerut, conform cerinței: dacă C = 1, numărul va reprezenta numărul maxim de termeni dintr-o descompunere, dacă C = 2, numărul va reprezenta numărul de valori din intervalul respectiv care pot fi descompuse cu un număr maxim de termeni, iar dacă C = 3, numărul va reprezenta acea valoare din intervalul respectiv care admite o descompunere cu un număr maxim de termeni, minimă din punct de vedere lexicografic.

Restricții și precizări

• 0 < N ≤ 1000
• 2 < A ≤ B ≤ 100 000
• Suma lungimilor intervalelor din toate seturile unui test nu va depăși 100 000.
• Pentru rezolvarea corectă a cerinței 1, se acordă 20% din punctaj, pentru cerința 2 se acordă 40% din punctaj, iar pentru cerința 3 se acordă 40% din punctaj.
• Pentru teste în valoare de 30 de puncte, N ≤ 50, B ≤ 1000 și suma lungimilor intervalelor din teste nu va depăși 10 000.

Exemplul 1:

multisum.in

1 1
50 60

multisum.out

5

Explicație

Există un singur set de date. Se rezolvă cerința 1. Descompunerile maximale ale numerelor din interval au unele 4 termeni, altele 5 termeni. Deci cel mai mare număr de termeni este 5 (și acesta se obține pentru numerele 55, 57, 58 și 59).

Exemplul 2:

multisum.in

1 2
50 60

multisum.out

4

Explicație

Există un singur set de date. Se rezolvă cerința 2. Numerele care se pot descompune într-un număr maxim de termeni sunt 55, 57, 58 și 59. Deci sunt 4 numere care admit o descompunere maximală.

Exemplul 3:

multisum.in

1 3
50 60

multisum.out

55

Explicație

Există un singur set de date. Se rezolvă cerința 3. Cele 4 numere care admit descompuneri maximale sunt:
55=1+2+4+16+32, 55=1+2+4+12+36, 55=1+2+4+8+40
57=1+2+6+12+36, 58=1+3+6+12+36, 59=1+2+8+16+32
Cea mai mică sumă din punct de vedere lexicografic este 1+2+4+8+40 și ea corespunde numărului 55.

Exemplul 4:

multisum.in

3 3
50 50
10 13
16 17

multisum.out

50
11
17

Explicație

Sunt 3 seturi de date. Se rezolvă cerința 3: Intervalul [50, 50] conține doar numărul 50 care admite o singură descompunere maximală (cu 4 termeni) și aceasta este minimă din punct de vedere lexicografic.
Dintre numerele din intervalul [10,13], numerele 10, 11 și 13 admit o descompunere cu un număr maxim de termeni (3 termeni), dar o descompunere maximală a lui 11 (1+2+8) este minimă din punct de vedere lexicografic. În intervalul [16,17] numerele admit câte două descompuneri maximale: 16=1+3+12, 16=1+5+10, 17=1+2+14, 17=1+4+12, iar descompunerea minimă din punct de vedere lexicografic este 1+2+14 și corespunde valorii 17.