import sys
read=sys.stdin.readline

n = int(read())
for _ in range(n):
    i,t=map(int,read().split())

    a,b=1,1
    cnt=2
    while True:
        a,b=b,(a+b)%t
        cnt+=1
        if a==1 and b==0: break
    print(i,cnt)

import sys
read=sys.stdin.readline
from collections import deque

h,w=map(int,read().split())
ch=list(list(map(int,read().split())) for _ in range(h))

dx=[1,0,0,-1]
dy=[0,1,-1,0]

point=deque([[0,0]])
outsideair=[]#치즈를 감싸는 공기 저장

while point:
    a,b=point.popleft()
    for x,y in zip(dx,dy):
        ax,by=a+x,b+y
        if 0<=ax<h and 0<=by<w and ch[ax][by]==0:
            point.append([ax,by])
            ch[ax][by]='*'
            #리스트를 프린트했을 때 사각형이 깨지지 않도록 하기위해 -1이 아닌 *로 변환했다.
            outsideair.append([ax,by])

time=0#치즈가 사라질때 까지 걸린 시간
disappear_tmp=0#이전 회차에서 사라진 치즈의 개수 저장
disappear=0#이번 회차에서 사라질 치즈의 개수

while True:
    disappear_tmp=disappear
    disappear=0
    outsideair_tmp=[]#치즈가 없어져 새로운 외부공기가 될 칸들을 저장

    #outsideair에 둘러쌓인 없어질 치즈들 탐색
    for a,b in outsideair:
        for x,y in zip(dx,dy):
            ax,by=a+x,b+y
            if 0<=ax<h and 0<=by<w and ch[ax][by]==1 and [ax,by] not in outsideair_tmp:
                outsideair_tmp.append([ax,by])
                disappear+=1

    tmp=[]
    #outsideair에 둘러쌓여 없어질 치즈들을 탐색한 후
    #치즈들이 녹고 나서 내부 공기가 외부 공기와 만날 수도 있기 때문에, 이런 공기들을 다시한번 탐색해 tmp에 저장한 후 outsideair_tmp에 추가해준다.
    for a,b in outsideair_tmp:
        ch[a][b]='*'
        point=deque([[a,b]])
        while point:
            a,b=point.popleft()
            for x,y in zip(dx,dy):
                ax,by=a+x,b+y
                #녹은 치즈들과 인접한 공기가 존재하면 이 공기들도 '*'로 변환
                if 0<=ax<h and 0<=by<w and ch[ax][by]==0:
                    point.append([ax,by])
                    ch[ax][by]='*'
                    tmp.append([ax,by])

    outsideair_tmp+=tmp
    outsideair=outsideair_tmp[::]
    #녹은 치즈가 없다면 while문 탈출!
    if outsideair==[]:
        print(time)
        print(disappear_tmp)
        break

    time+=1

import sys
# sys.stdin = open("input.txt","rt")
read=sys.stdin.readline
from collections import deque
n,m=map(int,read().split())
ch=list(list(map(int,read().split())) for _ in range(n))

dx=[1,0,0,-1]
dy=[0,1,-1,0]

outside=[]
def getOutside_air():
    point=deque([[0,0]])
    while point:
        a,b=point.popleft()
        for x,y in zip(dx,dy):
            ax,by=a+x,b+y
            if 0<=ax<n and 0<=by<m and ch[ax][by]==0:
                ch[ax][by]='*'
                point.append([ax,by])
                for xx,yy in zip(dx,dy):
                    axx,byy=ax+xx,by+yy
                    if 0<=axx<n and 0<=byy<m and ch[axx][byy]==1 and [ax,by] not in outside:
                        outside.append([ax,by])
                        break
    return

getOutside_air()
answer=0
while True:
    tmp_melt=[]
    tmp_melt_two=[]
    tmp_outside=[]

    for a,b in outside:
        for x,y in zip(dx,dy):
            ax,by=a+x,b+y
            if 0<=ax<n and 0<=by<m and ch[ax][by]==1:
                if [ax,by] not in tmp_melt: tmp_melt.append([ax,by])
                else: tmp_melt_two.append([ax,by])

    for a,b in tmp_melt_two:
        ch[a][b]='*'
        for x,y in zip(dx,dy):
            ax,by=a+x,b+y
            if 0<=ax<n and 0<=by<m and ch[ax][by]==0:
                point=deque([[ax,by]])
                while point:
                    i,j=point.popleft()
                    for xx,yy in zip(dx,dy):
                        ixx,jyy=i+xx,j+yy
                        if 0<=ixx<n and 0<=jyy<m and ch[ixx][jyy]==0:
                            ch[ixx][jyy]='*'
                            tmp_outside.append([ixx,jyy])
                            point.append([ixx,jyy])
                break
    tmp_outside+=tmp_melt_two

    if tmp_outside==[]:break
    outside+=tmp_outside
    answer+=1

    # for i in ch:
    #     print(*i)
    # print()

print(answer)