题目描述

对于正整数 $n$，定义 $f(n)$ 为 $n$ 所含质因子的最大幂指数。例如 $f(1960)=f(2^3\times 5^1\times 7^2)=3,f(10007)=1,f(1)=0$。 给定正整数 $a,b$，求下式的值：

输入格式

第一行一个数 $T$，表示询问数。

接下来 $T$ 行，每行两个数 $a,b$，表示一个询问。

输出格式

对于每一个询问，输出一行一个非负整数作为回答。

4
7558588 9653114
6514903 4451211
7425644 1189442
6335198 4957

35793453939901
14225956593420
4332838845846
15400094813

数据规模与约定

对于 $100\%$ 的数据，$1\leq T\leq 10^4$，$1\leq a,b\leq 10^7$。