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\}$.
# 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)
# 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)