Pour deux entiers strictement positifs quelconques $a$ et $b$, on définit la fonction $\texttt{gen_string}(a,b)$ par le code Python suivant :

def gen_string(a: int, b: int):
    res = ""
    ia, ib = 0, 0
    while ia + ib < a + b:
        if ia * b <= ib * a:
            res += '0'
            ia += 1
        else:
            res += '1'
            ib += 1
    return res

Code C++ équivalent :

string gen_string(int64_t a, int64_t b) {
    string res;
    int ia = 0, ib = 0;
    while (ia + ib < a + b) {
        if ((__int128)ia * b <= (__int128)ib * a) {
            res += '0';
            ia++;
        } else {
            res += '1';
            ib++;
        }
    }
    return res;
}

À la fin de la boucle, $ia$ vaut $a$ et $ib$ vaut $b$ ; cette fonction renvoie donc une chaîne binaire de longueur $a+b$ contenant exactement $a$ zéros et $b$ uns. Par exemple, $\texttt{gen_string}(4,10)=01110110111011$.

Une chaîne binaire $s$ est dite bonne s'il existe des entiers strictement positifs $x$ et $y$ tels que $s=\texttt{gen_string}(x,y)$. Étant donnés deux entiers strictement positifs $A$ et $B$ ($1\le A,B\le 10^{18}$), votre tâche consiste à calculer le nombre de bons préfixes de $\texttt{gen_string}(A,B)$. Par exemple, $\texttt{gen_string}(4,10)$ possède $6$ bons préfixes :

x = 1 | y = 1 | gen_string(x, y) = 01
x = 1 | y = 2 | gen_string(x, y) = 011
x = 1 | y = 3 | gen_string(x, y) = 0111
x = 2 | y = 5 | gen_string(x, y) = 0111011
x = 3 | y = 7 | gen_string(x, y) = 0111011011
x = 4 | y = 10 | gen_string(x, y) = 01110110111011

Entrée

La première ligne contient $T$ ($1\le T\le 10$), le nombre de cas de test indépendants.

Chacune des $T$ lignes suivantes contient deux entiers $A$ et $B$.

Sortie

La réponse à chaque cas de test sur une nouvelle ligne.

Exemples

Entrée 1

6
1 1
3 5
4 7
8 20
4 10
27 21

Sortie 1

1
5
7
10
6
13

Sous-tâches

• Entrée 2 : $A,B\le 100$
• Entrée 3 : $A,B\le 1000$
• Entrées 4-7 : $A,B\le 10^6$
• Entrées 8-13 : Toutes les réponses sont au plus $10^5$.
• Entrées 14-21 : Aucune contrainte supplémentaire.

Auteur du problème : Benjamin Qi