#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#define N 11000

int main()
{
    int T, m, n, l, r, cnt=1;
    scanf("%d", &T);

    while(T--)
    {
        l=r=0;
        scanf("%d%d", &m, &n);
        while(1)
        {
            if(m==1 && n==1)
                break;
            if(m<n)
            {
                if(n%m==0)
                {
                    r+=n/m-1;
                    n=1;
                }
                else
                {
                    r+=n/m;
                    n=n%m;
                }
            }
            if(m>n)
            {
                if(m%n==0)
                {
                    l+=m/n-1;
                    m=1;
                }
                else
                {
                    l+=m/n;
                    m=m%n;
                }
            }
        }
        printf("Scenario #%d:\n", cnt++);
        printf("%d %d\n\n", l, r);
    }
    return 0;
}