题目描述

您有一个空的 1 × n 网格。网格的单元格从左到右从 1 到 n 进行排列。您必须在网格中放入 m 个相同的硬币。一个单元格可以包含零个或多个硬币。如果您选择一对单元格，每个单元格至少包含一个硬币，则单元格之间的距离必须为质数。请问你可以用多少种方式放置硬币？由于答案可能很大，输出答案mod 10^9+7的结果。如果至少有一个单元格包含不同数量的硬币，则两种方式不同。下标为 i， j 的两个单元格之间的距离为 |i − j|。

输入

第一行包含 T （1 ≤ T ≤ 2000） （测试用例的数量）。接下来的每一行都包含两个整数 n （1 ≤ n ≤ 10^5 ） 和 m （1 ≤ m ≤ 10^5 ） ，用一个空格分隔。

输出

对于每个案例，打印案例编号和答案mod 10^9+7的值。