题目描述

若不想阅读题目背景，可直接跳转至最后一段。 公元前 490 年，希腊在马拉松战役取胜后，信使菲迪皮茨从马拉松平原奔跑约 40 公里抵达雅典宣告胜利，说完喜讯后便离世。为纪念此事，1896 年雅典首届现代奥运会将马拉松列为比赛项目，最初赛程约 40 公里。1908 年伦敦奥运会把赛程调整为 42.195 公里，该标准于 1921 年被世界田径联合会正式确定。女子马拉松项目则在 1984 年洛杉矶奥运会成为奥运会正式比赛项目。 马拉松运动极易让人身心俱疲。跑者通常会在 30 至 35 公里处遭遇撞墙期（体内糖原耗尽），体力与意志力双双濒临崩溃。长跑还极易损伤膝盖、脚踝、小腿等身体部位。除此之外，起跑阶段难以把控配速、赛程后半段是孤独的心理拉锯、天气变化影响体感、补给时机不当易引发肠胃不适与电解质紊乱。参加马拉松还需要日常进行系统的耐力与力量训练，毫无准备贸然参赛受伤风险极高。 而参加马拉松最大的难处，其实是极低的中签率。热门马拉松赛事中签率常不足 10%，新手参与中签率甚至仅有 2%。 假如你是马拉松新手，你认为跑马拉松最大的困难是什么？

正题：给定中签判定系数 N 和报名号码 M ，若 N 能够整除 M ，则判定抽签中签。现给出报名号码与判定系数，判断是否成功中签。

输入格式

第一行输入一个正整数 T （ 1≤T≤100 ），代表测试用例组数。 接下来 T 行，每行输入两个正整数 M,N （ 1≤M,N≤100000 ），分别代表报名号码 M 和抽签判定系数 N 。

输出格式

对于每组测试用例，单独输出一行整数： 中签输出 1，未中签输出 0。

Samples

2
2026 2026
2 2025

1
0

Limitation

1s, 1024KiB for each test case.