Sonsuz Ağac

Link-Cut planet sistemindəki uçuşunuz zamanı sənə darıxdıqda, Lucy səninlə nüvə fizikası barədə danışmağa başladı! Xüsusilə, gəmiləndəki reaktorda zincir reaksiyaların necə işlədiyini.

Gəmi adi olmadığı üçün, reaktor da adi deyil; o, hər birinin öz xüsusiyyəti olan unikal atomlar yaradır, məsələn, müsbət tam ədəd. Yeni bir atom yarandıqda, o, ən kiçik işğal olunmamış xüsusiyyət dəyərini seçir (bunu da onun əvvəl mövcud olan atomların sayından bir artıq nömrə kimi düşünə bilərsiniz). İlk olaraq, reaktor bir atom (nömrəsi 1 olan) yaradır, sonra fission mərhələsi başlayır.

Atomlar, onların xüsusiyyətlərinin sırasına görə, ədəd $f(x)$ qədər əlavə atom yaradır, burada $f(x)$ $x$-in ikili təsvirindəki dəyişdirilmiş bitlərin sayını ifadə edir, formal olaraq bu belə təyin edilə bilər:

burada $l(x)$ $x$-in $2^y$ tərəfindən böldüyü ən böyük qeyri-mənfi tam ədəd $y$-dır.

Bu əməliyyatlar bir zincir reaksiya ağacı təşkil edir. Lakin, belə bir quruluş çox sabit deyil, beləliklə arızalar tez-tez baş verir. Hər bir arıza iki atom tərəfindən (xüsusiyyətləri xüsusiyyətləri ilə) təyin edilə bilər, və hər bir arızada, bu iki atom arasındakı yol üzərindəki bütün əlaqələr ləğv edilir. Reaktorun vəzifəsi onları bərpa etməkdir, ki, bu da çox mürəkkəb bir prosesdir, beləliklə biz ən sadə hissəsinə, yəni, zərur olan enerji hesablamasına fokuslanacağıq, ki, bu da ləğv edilmiş əlaqələrin sayına bərabərdir.

Bu ağacın bir hissəsi

Bu nöqtədə, bir asteroid gəmini vurdu, və Lucy zərəri düzəltməyə qədəm atdı, sənə də enerji hesablaması üçün proqram yazma tapşırığı verdi. Sən hələ də öyrənirsiniz, beləliklə o, arızaların yalnız $n$-dən kiçik xüsusiyyətə malik atomlar arasında baş verəcəyini deyərək tapşırığı sadələşdirdi.

Son tarix yaxınlaşır, beləliklə gecikməyin və tapşırığınızı yerinə yetirin.

Giriş verilənləri

İlk sətir $n$ və $q$ $(2\le n\le 10^{15},1\le q\le 10^4)$ olmaqla iki tam ədəd içərər — hər bir arızada ən böyük xüsusiyyət dəyəri və arızaların sayı.

Növbəti $q$ sətirdən hər biri iki tam ədəd $v$ və $u$ $(1\le v\le n,1\le u\le n,v\ne u)$ içərər — arızanın baş verdiyi iki atomun xüsusiyyət dəyəri. Xahiş edirəm qeyd edin ki, hər bir sorğu digərlərindən asılı deyil.

Çıxış verilənləri

Hər bir arızada, ləğv edilmiş əlaqələrin sayını çıxarın.

Nümunələr

Qiymətləndirmə

1. ($24$ xal): $n\le 100$;

2. ($23$ xal): $n\le 10^6$;

3. ($59$ xal): $n\le 10^{12}$;

4. ($19$ xal): əlavə məhdudiyyətlər yoxdur;