中竞（浙江）教育成立于2017年，其发展主体为实现互联网企业与教育领域共同携手打破传统教育模式。致力于游戏产业人才的全方位布局，全力解决“大学生就业难、企业用人难”这一紧迫问题。
中竞教育全力为员工谋福利，在某个国家，税收制度特别奇怪，个人所得税等于金额的因子中比金额本身小且最大的那个。每个人可以把工资最多分成k份整数分别交税且每份工资至少为2。
中竞的财务部门想尽可能的把税收变少，假设员工每个月的工资为n，最多分为k份工资，作为过来面试的你，需要回答税收最少是多少。
为了帮助你更好的解决问题，财务部门给你提供了以下的小信息。
Goldbach's conjecture is one of the oldest and best-known unsolved problems in number theory and all of mathematics. It states:
Every even integer greater than 2 can be expressed as the sum of two primes.
The conjecture has been shown to hold for all integers less than 4 × 1018, but remains unproven despite considerable effort.
From Wikipedia
多组样例
第一行一个整数T(T<=1000)代表测试样例数。
接下来T行,每行一个大于1的正整数n(n<=109),和一个正整数k(1<=k<=20)。
输出T个整数，表示员工最少要交多少税。