Problem Description

给定正整数 $n,m$，求有多少个长度为 $m$ 的序列 $i_1,i_2,…,i_m$，满足 $\forall 1 \leq x \leq m,i_x \in [1,n]$，且$\text{lcm}(i_1,i_2,…,i_m)=n$，答案对 $998244353$ 取模。

Input

本题共有 $T$ 组数据。

输入第一行，包含一个正整数，表示 $T$。

之后对于每组数据，输入 $1$ 行，包含 $2$ 个正整数 $n,m$。

#### 评测数据规模

对于所有测评数据，$1 \leq T \leq 10^3,1 \leq n,m \leq 10^9$。

Output

输出共 $T$ 行，每行输出 $1$ 个整数，表示最终答案，答案对 $998244353$ 取模。

4
1 2
3 4
5 6
7 8

1
15
63
255