#P3733. [Pa2013]Iloczyn

    ID: 2587 传统题 1000ms 128MiB 尝试: 878 已通过: 178 难度: 5 上传者: 标签>CF1700普及+/提高-约数成对枚举回溯搜索对称性去重可行性剪枝

[Pa2013]Iloczyn

[PA2013] Iloczyn

题目描述

给定正整数 nn 和 kk,问能否将 nn 分解为 kk 个不同正整数的乘积。

输入格式

第一行一个数 TT 表示测试组数。

接下来 TT 行每行两个数 n,kn,k。

输出格式

输出 TT 行,若可以被分解,输出 TAK 否则输出 NIE。

样例 #1

样例输入 #1

3
15 2
24 4
24 5

样例输出 #1

TAK
TAK
NIE

提示

对于 100%100\% 的数据,1≤T≤4×1031\le T\le 4\times 10^3,1≤n≤1091\le n\le 10^9,1≤k≤201\le k\le 20。