Chef wants to select a subset $S$ of the set $\{1, 2, \ldots, N\}$ such that there are no two integers $x, y \in S$ which satisfy $\frac{x}{y} = M$.
Help Chef find the maximum size of a subset $S$ he can choose and the number of ways in which he can choose a subset $S$ with this maximum size. Since the number of ways to choose $S$ can be very large, calculate it modulo $998,244,353$.

-----Input-----
- The first line of the input contains a single integer $T$ denoting the number of test cases. The description of $T$ test cases follows.
- The first and only line of each test case contains two space-separated integers $N$ and $M$.

-----Output-----
For each test case, print a single line containing two space-separated integers ― the maximum size of a subset Chef can choose and the number of ways to choose a subset with this maximum size modulo $998,244,353$. Note that only the number of ways to choose a subset should be printed modulo $998,244,353$.

-----Constraints-----
- $1 \le T \le 10,000$
- $2 \le M \le N \le 10^{18}$

-----Example Input-----
3
5 2
10 2
100 3

-----Example Output-----
4 1
6 12
76 49152

-----Explanation-----
Example case 1: The only subset $S$ with the maximum size which Chef can choose is $\{1, 3, 4, 5\}$.

Difficulty: interview

Starter code:

Solutions:
for _ in range(int(input())):
 N,M = list(map(int,input().split()))
 count,e,perm = 0,0,1
 while(True):
  lim,start = N//(M**e),N//(M**(e + 1)) + 1
  num = lim - start + 1
  divs = num//M
  if((start + divs*M) <= lim):
   r = (start+divs*M)%M
   if(r == 0 or (r + (lim - (start + divs*M)) >= M)):
    divs += 1
  cmon = num - divs
  if(e % 2 == 0):
   count += cmon*((e+2)//2)
  else:
   count += cmon*(e//2 + 1)
   perm = (perm * pow((e + 3)//2,cmon ,998244353))%998244353
  e += 1
  if(start == 1):
   break
 print(count,perm)


ts = int(input())
for _ in range(ts):
 n, m = map(int, input().split())
 t, tt, res, cnt = 1, [], 0, 1
 while t <= n:
  t *= m
  v = n // t
  v -= v // m
  if tt:tt[-1] -= v
  tt.append(v)
 for i, v in enumerate(tt):
  res += ((i + 2) // 2) * v
  if i & 1 == 0:
   cnt = cnt * pow((i + 2) // 2 + 1, v, 998244353) % 998244353
 print(n - res, cnt)

import sys
sys.setrecursionlimit(10**9)
mod = 998244353
def power(a, b):
 res=1
 while(b>0):
  if(b%2):
   res*=a
   res%=mod
  b//=2
  a*=a
  a%=mod
 return res
def solve(a):
 if(a>n):
  return (0,1)
 val = a
 c=1
 p=1
 size=0
 ways=0
 while(1):
  if(val>(n//m)):
   break
  val *= m
  p *= m
  c += 1
 u = n//p
 ans = solve(u+1)
 rem = u//m
 rem -= (a-1)//m
 u -= rem
 size = ((c+1)//2)*(u-a+1)
 if(c%2):
  ways=1
 else:
  ways = power(c//2+1,u-a+1)
 size += ans[0]
 ways *= ans[1]
 ways %= mod
 #print(a,ways,size)
 return (size,ways)
t = int(input())
while(t):
 t -= 1
 n, m = list(map(int,input().split()))
 ans = solve(1)
 print(ans[0],ans[1])


#dt = {} for i in x: dt[i] = dt.get(i,0)+1
import sys;input = sys.stdin.readline
inp,ip = lambda :int(input()),lambda :[int(w) for w in input().split()]

M = 998244353
for _ in range(inp()):
 n,m = ip()
 size,ways = 0,1
 a,b = 1,m
 for k in range(1,70):
  if a > n:
   break
  ct = (n//a - n//b) - (n//a//m - n//b//m)
  size += ct*((1+k)//2)
  if k%2 == 0:
   ways = (ways*pow(k//2 +1,ct,M))%M
  a,b = a*m,b*m
 print(size,ways)


# cook your dish here
for _ in range(int(input())):
 n, k = map(int, input().split())
 t = 1
 tt = []
 while t <= n:
  t *= k
  v = n // t
  v -= v // k
  if tt:
   tt[-1] -= v
  tt.append(v)
 res, cnt = 0, 1
 for i, v in enumerate(tt):
  res += ((i + 2) // 2) * v
  if i & 1 == 0:
   cnt = cnt * pow((i + 2) // 2 + 1, v, 998244353) % 998244353
  #print("->", res, cnt)    
 print(n - res, cnt)

def groupsInInterval(L,R,M,N):
 if(R<=N):
  return (R - (L-1)) -(R//M - (L-1)//M)
 else:
  return 0
def power(a,b):
 # print(a,'**',b, a**b)
 MOD = 998244353
 res = 1
 while(b>0):
  # print('a = ', a,"b = ",b)

  if(b%2):
   res*=a
   res%=MOD
  b//=2
  a*=a
  a%=MOD
 # print('res',res)
 return res

while(True):
 try:
  test = int(input())
 except EOFError:
  break
 for i in range (test):
  MOD = 998244353
  n,m = list(map(int,input().split()))
  taken,ways = 0,1
  for i in range(1,70):
   # print(ways)
   L = n//m**i + 1;
   R = n//m**(i-1)
   groups = groupsInInterval(L,R,m,n)
   if(i%2==0):
    taken+= (i//2 )*groups
    # print("ways ",ways)
    ways*= power((i//2 +1),groups)
    # ways*= ((i//2 +1)**groups)
   else:
    taken+= ((i+1)//2)*groups
    ways *= (1)
  print(taken,ways%MOD)


def help():
 n,m = map(int,input().split(" "))
 max_power = 0

 n1 = n
 while n1>=m:
  n1 = n1//m
  max_power += 1
 sizes = [0]*(max_power+1)

 sizes[max_power] = n//(m**max_power)
 yet = sizes[max_power]
 
 curr = max_power-1
 while curr>=0:
  y1 = n//(m**curr)
  sizes[curr] = y1 - yet
  yet = y1
  curr -= 1

 size = [0]*(max_power+1)
 for i in range(max_power,-1,-1):
  curr = sizes[i]
  size[i] = curr
  for j in range(max_power+1):
   sizes[j] -= curr
 size_ans = 0
 ways_ans = 1
 for i in range(max_power+1):
  C = i+1
  size_ans += size[i]*((C+1)//2)

  if(C%2 == 0):
   ways_ans *= pow((C//2) + 1,size[i],998244353)
   ways_ans = ways_ans % 998244353
 print(size_ans,ways_ans)


for _ in range(int(input())):
 help()