题目背景

两个整数相除的商，有可能整除没有小数，有可能能除尽含有限小数，也有可能不能除尽含有无限循环小数。

题目描述

小智学习除法的时候，发现商有些没有小数，有些含有有限小数，有些是无限小数。

小智想请你编程帮她找一下除法得到的商的规律。

输入格式

两行。

第一行一个整数 $t$，表示下面有 $t$ 组数据。

接下来的 $t$ 行里面，每行含两个正整数 $m$ 和 $n$ ，空格隔开。表示被除数和除数。

输出格式

$t$ 行，每行包含一个整数，表示输入的后面 $t$ 行两个正整数相除的商的类型。整数只有以下三种情况。

数字 $0$ - 表示商没有小数；

数字 $1$ - 表示商含有有限小数；

数字 $2$ - 表示商含有无限小数。

样例 #1

3
72 9
7 56
10 3

0
1
2

说明/提示

对于 $20\%$ 数据，$1 \le t \le100，1 \le m,n \le 100$；

对于 $50\%$ 数据，$1\le t \le 10000，1 \le m,n \le 10000$；

对于 $100\%$ 数据，$1 \le t \le 10^6，1 \le m,n \le 10^7$。