#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N=1e4+3;
int x,L;
int biao[N]={0,1,1,1,1001,1001,2,2,2,2,2,3,11,1001,1001,2,2,2,3,3,3,86,1001,1001,2,3,3,3,3,3,1001,1001,1001,1001,3,3,3,4,4,1001,1001,1001,1001,3,1001,4,3,8,31,1001,1001,796,1001,3,3,3,4,4,1001,1001,5,5,3,4,4,4,4,1001,1001,5,21,4,4,4,1001,1001,1001,1001,55,35,4,3,14,4,1001,1001,1001,1001,5,7,4,4,4,7,1001,1001,22,5,5,4,7,83,239,1001,1001,1001,5,51,1001,5,1001,892,1001,1001,1001,11,5,5,4,7,92,1001,1001,5,5,5,5,5,4,4,1001,1001,5,5,5,7,4,13,103,1001,1001,5,1001,1001,5,10,10,67,1001,1001,367,5,5,5,7,4,1001,1001,1001,130,5,31,5,30,58,1001,1001,1001,32,8,8,87,1001,1001,8,1001,1001,8,15,5,1001,5,14,17,1001,1001,5,58,5,5,5,7,1001,1001,1001,1001,8,5,49,24,6,182,1001,1001,14,21,11,6,6,6,7,1001,1001,1001,6,6,5,6,6,7,1001,1001,37,5,6,6,7,1001,1001,1001,1001,1001,6,32,143,6,565,1001,1001,1001,29,10,5,6,6,7,26,1001,1001,5,5,5,7,5,42,442,1001,1001,5,11,13,9,1001,10,1001,1001,1001,11,1001,53,6,7,6,1001,1001,1001,1001,5,7,6,6,6,7,1001,1001,1001,493,7,6,7,1001,1001,1001,1001,8,174,8,8,10,336,59,1001,1001,49,8,17,7,6,7,37,1001,1001,1001,41,5,7,7,7,1001,1001,1001,1001,9,8,7,65,24,7,1001,1001,11,11,11,6,7,7,7,1001,1001,11,6,6,6,7,6,7,1001,1001,1001,6,7,7,7,499,13,1001,1001,1001,11,7,65,78,7,10,1001,1001,1001,1001,6,7,7,7,47,1001,1001,5,16,26,7,27,7,59,1001,1001,62,8,9,8,8,12,1001,1001,1001,97,9,8,10,7,11,7,1001,1001,1001,164,7,6,7,7,7,1001,1001,46,18,9,8,7,487,506,1001,1001,1001,8,14,26,6,33,97,1001,1001,307,31,6,6,6,7,1001,1001,1001,131,1001,6,7,13,78,1001,1001,1001,1001,8,8,9,22,1001,14,1001,1001,8,72,10,6,7,10,1001,1001,1001,13,6,7,7,7,7,7,1001,1001,17,8,7,11,1001,9,10,1001,1001,14,27,8,8,10,10,10,1001,1001,50,8,489,7,6,29,1001,1001,1001,1001,185,23,8,8,15,1001,1001,1001,101,8,8,8,8,10,1001,1001,1001,8,8,8,12,13,23,35,1001,1001,8,20,1001,8,7,13,1001,1001,1001,28,8,8,8,28,1001,223,1001,1001,14,8,14,45,15,7,10,1001,1001,14,1001,6,7,7,7,7,1001,1001,1001,21,8,7,10,79,551,1001,1001,8,14,11,8,8,219,1001,1001,1001,74,1001,8,40,7,20,1001,1001,1001,260,186,7,11,39,9,1001,1001,1001,1001,9,9,8,9,9,1001,1001,1001,1001,8,14,9,10,10,19,1001,1001,1001,33,26,528,7,7,110,1001,1001,1001,1001,8,10,9,15,1001,1001,1001,8,8,8,8,430,1001,1001,1001,1001,8,218,15,6,10,13,142,1001,1001,92,47,10,9,10,7,1001,1001,1001,1001,8,9,9,21,9,11,1001,1001,14,9,11,9,201,957,7,1001,1001,1001,1001,27,7,7,7,7,1001,1001,164,637,9,56,7,15,1001,1001,1001,62,15,8,9,9,10,1001,1001,1001,1001,23,9,36,14,7,25,1001,1001,116,1001,104,8,9,9,77,1001,1001,1001,8,8,8,8,9,1001,1001,1001,1001,8,9,9,13,12,13,1001,1001,14,9,23,339,9,21,7,1001,1001,17,1001,8,9,9,1001,83,1001,1001,8,14,9,1001,9,1001,44,1001,1001,59,11,94,64,7,10,1001,1001,1001,32,957,10,9,10,9,1001,1001,1001,1001,9,8,8,9,9,1001,1001,1001,19,601,14,9,13,94,1001,1001,1001,98,166,17,22,7,13,1001,1001,1001,17,17,11,11,9,908,22,1001,1001,17,1001,9,8,429,1001,10,1001,1001,1001,15,706,20,17,13,1001,1001,1001,11,17,16,9,8,10,70,1001,1001,175,8,8,8,8,9,13,1001,1001,1001,9,8,138,13,13,10,1001,1001,1001,559,10,10,10,10,10,1001,1001,395,1001,9,8,10,1001,1001,1001,1001,53,288,14,14,18,13,1001,1001,1001,1001,9,11,33,14,7,1001,1001,1001,1001,88,1001,10,35,17,1001,1001,1001,1001,37,35,9,8,18,1001,1001,1001,11,20,385,18,10,56,13,1001,1001,1001,12,10,10,9,28,10,1001,1001,17,25,8,9,9,9,1001,1001,1001,26,14,9,41,1001,13,922,1001,1001,184,11,15,10,1001,10,1001,1001,1001,1001,45,1001,9,10,10,1001,1001,1001,1001,9,8,10,1001,18,10,1001,1001,11,11,11,11,10,10,10,1001,1001,11,153,10,10,10,10,10,1001,1001,341,59,10,9,9,1001,1001,1001,1001,1001,11,10,14,89,10,1001,1001,1001,527,8,8,10,10,10,7,1001,1001,8,17,1001,10,293,10,1001,1001,1001,1001,12,14,15,9,41,1001,1001,1001,1001,8,11,15,10,1001,10,1001,1001,14,11,10,35,10,9,10,1001,1001,1001,21,9,8,9,9,1001,1001,1001,20,1001,378,9,11,13,1001,1001,1001,361,24,11,48,37,10,1001,1001,1001,179,26,15,10,9,67,310,1001,1001,119,137,28,11,1001,1001,1001,1001,1001,11,11,9,9,10,1001,32,1001,1001,1001,11,10,10,10,10,10,1001,1001,1001,36,10,70,15,9,1001,1001,1001,20,14,11,15,1001,24,1001,1001,1001,8,1001,15,10,42,88,1001,1001,1001,1001,186,17,9,11,50,1001,1001,1001,1001,20,10,13,22,1001,13,1001,1001,23,9,15,11,40,14,44,1001,1001,832,15,29,24,10,23,58,1001,1001,1001,17,13,9,8,146,734,1001,1001,11,11,11,11,11,10,13,1001,1001,23,187,9,10,10,10,10,1001,1001,1001,26,49,10,23,226,56,1001,1001,1001,48,14,9,21,1001,1001,1001,1001,1001,8,9,9,10,1001,392,1001,1001,1001,9,10,1001,13,21,257,1001,1001,1001,1001,11,12,13,18,1001,1001,1001,11,11,9,21,11,10,98,1001,1001,11,14,11,18,10,10,338,1001,1001,1001,1001,14,19,9,25,1001,1001,1001,1001,11,444,10,438,46,1001,1001,1001,1001,11,11,9,31,788,1001,1001,1001,218,11,26,24,11,10,22,1001,1001,1001,12,11,11,11,21,1001,1001,1001,11,11,11,11,9,97,10,1001,1001,11,11,11,10,10,10,10,1001,1001,11,1001,14,11,10,16,16,1001,1001,1001,11,11,11,15,1001,1001,1001,1001,187,9,8,11,74,10,19,1001,1001,35,15,46,12,13,16,17,1001,1001,1001,12,11,10,10,22,1001,1001,1001,11,12,9,11,11,12,1001,1001,1001,14,21,11,13,14,44,10,1001,1001,53,1001,12,13,14,9,1001,1001,1001,1001,88,14,11,23,26,1001,1001,1001,1001,11,39,9,10,1001,19,1001,1001,29,18,20,14,13,40,1001,1001,1001,1001,219,10,12,9,22,1001,1001,1001,11,11,9,9,9,13,1001,1001,1001,11,1001,9,13,10,13,1001,1001,1001,1001,17,38,13,14,12,625,1001,1001,1001,11,20,9,96,1001,10,1001,1001,182,23,77,50,13,116,1001,1001,1001,11,44,68,14,10,350,1001,1001,1001,1001,12,10,10,10,593,1001,1001,1001,23,23,10,15,9,995,1001,1001,1001,23,14,115,17,56,13,83,1001,1001,40,17,14,10,13,88,1001,1001,1001,89,11,11,11,11,54,23,1001,1001,623,11,905,243,76,10,13,1001,1001,140,890,17,15,31,16,71,1001,1001,1001,117,11,23,10,57,235,1001,1001,11,1001,9,9,25,1001,217,1001,1001,1001,714,22,13,45,12,143,1001,1001,1001,12,12,11,12,10,1001,1001,1001,26,31,11,11,91,27,1001,1001,1001,1001,993,14,15,13,913,34,1001,1001,1001,11,257,14,12,15,28,1001,1001,68,25,10,13,15,33,1001,1001,1001,23,147,15,11,15,24,14,1001,1001,20,1001,15,12,10,13,29,1001,1001,11,12,12,10,11,12,1001,1001,1001,68,11,11,9,11,25,13,1001,1001,14,50,11,43,13,13,10,1001,1001,1001,15,12,42,12,21,16,1001,1001,85,910,12,11,10,39,1001,1001,1001,20,29,12,57,15,12,1001,1001,1001,17,11,11,12,12,10,1001,1001,1001,418,12,12,10,10,10,1001,1001,1001,721,12,12,10,11,1001,1001,1001,1001,14,12,14,120,12,1001,13,1001,1001,14,9,12,12,10,18,1001,1001,1001,1001,1001,11,27,12,59,1001,1001,1001,1001,14,15,21,25,1001,74,1001,1001,11,591,429,12,1001,10,28,1001,1001,1001,12,13,12,12,10,1001,1001,1001,211,37,11,12,9,25,1001,1001,1001,83,39,14,25,13,13,73,1001,1001,259,11,17,33,11,209,19,1001,1001,1001,18,12,13,15,1001,1001,1001,1001,65,113,11,1001,17,33,233,1001,1001,11,11,11,12,13,92,1001,1001,1001,11,12,12,10,10,12,1001,1001,1001,1001,12,13,15,64,25,13,1001,1001,14,11,357,286,24,959,10,1001,1001,14,94,12,13,19,92,29,1001,1001,26,1001,14,11,27,1001,64,1001,1001,1001,12,71,16,16,13,1001,1001,1001,29,23,11,95,36,50,1001,1001,1001,1001,1001,1001,12,13,15,58,1001,1001,415,26,14,13,17,20,1001,1001,1001,77,11,71,11,10,39,19,1001,1001,1001,87,12,12,10,12,13,1001,1001,26,14,12,17,13,104,68,1001,1001,26,14,60,15,142,1001,1001,1001,1001,11,1001,9,12,291,10,1001,1001,1001,32,12,13,13,13,13,1001,1001,1001,1001,17,11,13,15,1001,10,1001,1001,1001,11,1001,1001,10,10,10,1001,1001,1001,624,681,12,10,882,19,1001,1001,1001,14,14,14,11,1001,845,1001,1001,38,14,10,35,75,10,13,1001,1001,23,15,11,19,1001,15,1001,1001,1001,884,1001,14,15,12,13,1001,1001,1001,1001,17,35,11,28,1001,1001,1001,1001,14,11,11,11,31,12,10,1001,1001,1001,11,12,12,12,10,13,1001,1001,26,1001,33,12,13,16,1001,1001,1001,1001,62,11,18,121,874,119,1001,1001,29,241,163,1001,12,13,1001,1001,1001,1001,20,17,13,14,15,1001,1001,1001,1001,15,12,11,22,803,82,1001,1001,1001,31,518,11,10,77,25,1001,1001,1001,1001,13,13,13,12,13,1001,1001,1001,14,13,14,13,25,26,1001,1001,17,455,11,21,47,19,1001,1001,1001,149,90,15,12,17,13,524,1001,1001,1001,20,14,13,13,13,1001,1001,1001,1001,12,17,13,28,1001,13,1001,1001,1001,11,11,9,13,13,13,1001,1001,1001,1001,13,12,13,13,13,1001,1001,1001,133,13,13,11,711,1001,1001,1001,248,1001,12,42,97,10,1001,1001,1001,1001,29,51,13,13,13,161,1001,1001,1001,1001,14,12,14,13,1001,1001,1001,1001,12,12,10,16,79,1001,1001,1001,1001,12,126,15,13,346,13,1001,1001,14,367,13,14,13,13,13,1001,1001,22,1001,11,25,13,28,1001,1001,1001,269,14,11,21,40,31,1001,1001,1001,1001,1001,38,1001,12,13,19,1001,1001,1001,20,17,13,14,1001,1001,1001,1001,818,30,15,11,22,151,533,1001,1001,1001,15,14,25,13,628,380,1001,1001,11,1001,13,13,11,13,13,1001,1001,1001,84,11,11,11,26,1001,1001,1001,14,21,11,649,23,65,10,1001,1001,104,14,15,13,56,15,16,1001,1001,11,1001,14,11,15,22,1001,1001,1001,47,12,13,15,16,16,1001,1001,1001,17,14,15,15,1001,1001,53,1001,1001,28,15,20,12,13,15,1001,1001,1001,47,672,12,21,11,1001,1001,1001,1001,14,14,14,11,30,13,1001,1001,1001,14,21,286,13,13,12,13,1001,1001,1001,614,19,13,27,42,98,1001,1001,1001,14,21,12,1001,22,1001,1001,1001,29,29,29,15,13,1001,1001,1001,1001,29,11,13,14,12,27,377,1001,1001,1001,478,11,12,10,1001,1001,1001,1001,26,14,12,21,101,13,1001,1001,1001,20,14,405,37,13,13,1001,1001,1001,1001,62,26,12,28,30,1001,1001,1001,1001,38,48,13,14,394,1001,1001,1001,1001,15,14,1001,1001,82,1001,1001,1001,1001,15,142,20,10,13,256,1001,1001,47,1001,23,14,12,654,22,1001,1001,14,14,13,14,25,411,13,1001,1001,754,14,11,13,13,13,13,1001,1001,1001,17,59,11,13,37,1001,1001,1001,1001,64,14,15,112,17,1001,1001,1001,29,23,23,29,45,13,452,1001,1001,35,11,20,51,14,18,23,1001,1001,1001,43,12,12,13,1001,43,1001,1001,358,57,15,14,1001,13,1001,1001,1001,11,73,130,46,42,12,13,1001,1001,1001,48,1001,30,14,28,1001,1001,1001,14,14,14,14,14,22,1001,1001,1001,80,65,14,16,13,1001,79,1001,1001,32,11,99,1001,15,154,22,1001,1001,41,28,13,14,15,22,22,1001,1001,17,14,11,1001,22,24,31,1001,1001,11,11,11,12,13,13,1001,1001,1001,11,1001,14,12,11,19,1001,1001,1001,14,14,14,13,14,47,13,1001,1001,14,11,14,52,23,107,1001,1001,1001,910,1001,19,21,12,1001,1001,1001,1001,1001,14,13,13,13,16,22,1001,1001,17,12,13,14,36,12,433,1001,1001,17,14,11,12,12,10,133,1001,1001,82,1001,14,12,14,15,1001,1001,1001,14,14,14,14,14,1001,34,1001,1001,14,12,14,66,12,13,1001,1001,1001,14,32,19,14,19,16,16,1001,1001,106,14,14,14,13,47,1001,1001,1001,1001,14,17,14,871,31,19,1001,1001,11,470,11,19,31,12,1001,1001,1001,1001,310,14,13,12,13,1001,1001,1001,14,27,14,14,14,1001,160,1001,1001,134,1001,14,59,31,357,149,1001,1001,119,998,577,33,19,15,1001,1001,1001,26,24,13,14,15,1001,1001,1001,1001,17,14,11,238,1001,199,1001,1001,1001,23,30,32,12,13,15,338,1001,1001,157,37,14,13,15,15,37,1001,1001,14,14,14,14,14,1001,1001,1001,1001,14,11,23,53,129,124,13,1001,1001,1001,15,19,153,15,46,542,1001,1001,1001,14,20,17,13,1001,1001,1001,1001,20,23,15,15,1001,1001,460,1001,1001,14,21,116,31,21,13,352,1001,1001,1001,1001,79,13,13,13,1001,1001,1001,1001,17,14,12,168,1001,1001,1001,1001,1001,77,93,15,12,659,19,1001,1001,29,32,26,14,13,30,20,1001,1001,1001,14,14,14,14,18,1001,1001,1001,19,14,12,23,99,19,1001,1001,1001,32,32,15,19,1001,13,1001,1001,1001,32,1001,14,15,15,13,22,1001,1001,14,12,49,37,28,1001,10,1001,1001,322,32,11,61,31,32,65,1001,1001,1001,166,17,14,13,21,961,1001,1001,68,1001,14,14,32,1001,1001,1001,1001,62,15,12,15,15,283,1001,1001,1001,40,14,31,470,34,15,28,1001,1001,118,1001,46,12,13,172,833,1001,1001,175,12,12,11,18,1001,13,1001,1001,1001,12,68,19,17,12,13,1001,1001,14,155,109,36,14,16,143,1001,1001,1001,14,12,14,14,18,1001,1001,1001,29,1001,14,15,16,260,428,1001,1001,32,1001,15,33,19,26,16,1001,1001,23,24,12,14,18,18,1001,1001,1001,1001,17,23,12,249,15,1001,1001,1001,38,14,14,15,13,31,281,1001,1001,1001,389,1001,14,13,511,65,1001,1001,1001,511,24,1001,14,18,148,1001,1001,1001,15,15,15,15,33,1001,1001,1001,92,29,15,20,17,13,125,1001,1001,11,20,14,17,49,1001,1001,1001,1001,343,12,13,12,91,226,13,1001,1001,14,17,1001,230,13,13,13,1001,1001,1001,489,24,109,13,15,107,1001,1001,1001,1001,14,14,181,28,1001,1001,1001,38,65,13,43,15,13,1001,1001,1001,17,14,16,69,14,33,266,1001,1001,1001,43,17,12,490,15,91,1001,1001,1001,15,14,15,15,15,1001,1001,1001,14,14,14,15,29,1001,13,1001,1001,14,1001,17,49,19,13,1001,1001,1001,1001,1001,12,52,15,1001,1001,1001,1001,26,14,15,77,37,699,35,1001,1001,14,18,1001,20,1001,36,50,1001,1001,1001,24,741,14,18,1001,1001,1001,1001,1001,15,15,13,47,15,1001,1001,1001,1001,15,14,15,13,1001,265,1001,1001,1001,481,27,1001,11,200,25,1001,1001,80,33,15,304,15,84,1001,1001,1001,1001,14,15,14,15,40,1001,1001,1001,1001,35,15,69,260,15,58,1001,1001,1001,163,21,15,15,15,1001,1001,1001,566,15,15,15,15,15,1001,1001,1001,14,15,15,15,24,19,797,1001,1001,1001,11,12,62,13,29,1001,1001,1001,1001,66,14,12,13,630,1001,1001,1001,59,14,15,684,15,13,1001,1001,1001,344,23,18,19,21,137,1001,1001,1001,1001,83,21,12,14,15,614,1001,1001,1001,15,21,13,15,15,52,1001,1001,1001,17,14,15,12,1001,25,1001,1001,1001,1001,12,12,12,21,25,1001,1001,1001,75,12,14,15,46,1001,1001,1001,1001,14,14,14,1001,19,1001,1001,1001,44,14,208,12,19,19,1001,1001,1001,32,38,133,15,21,16,1001,1001,1001,1001,15,14,13,15,15,262,1001,1001,35,15,35,18,19,33,1001,1001,1001,77,197,17,24,12,1001,25,1001,1001,1001,22,13,13,13,545,1001,1001,1001,605,84,13,14,22,1001,13,1001,1001,1001,15,46,27,1001,19,16,1001,1001,407,26,21,13,136,59,1001,1001,1001,17,195,14,15,36,1001,367,1001,1001,17,12,35,22,17,338,71,1001,1001,35,23,12,13,15,16,16,1001,1001,1001,1001,15,15,13,15,1001,1001,1001,242,14,14,18,50,73,19,1001,1001,20,155,18,17,14,16,1001,1001,1001,244,1001,161,15,14,25,1001,1001,1001,28,15,125,16,38,125,1001,1001,1001,1001,18,18,18,317,817,271,1001,1001,1001,18,107,21,15,28,22,1001,1001,1001,21,13,15,13,36,1001,1001,1001,167,56,11,18,20,13,1001,1001,1001,886,1001,15,12,71,19,592,1001,1001,722,26,14,26,37,24,41,1001,1001,119,20,14,33,15,1001,179,1001,1001,35,17,175,16,19,1001,1001,1001,1001,1001,15,17,35,13,15,271,1001,1001,1001,27,15,14,15,15,26,1001,1001,116,301,22,15,43,12,1001,1001,1001,14,21,1001,17,14,485,79,1001,1001,1001,1001,14,13,14,1001,478,1001,1001,49,26,14,16,16,310,1001,1001,1001,700,14,15,15,19,1001,16,1001,1001,14,1001,41,14,15,21,479,1001,1001,857,77,20,16,22,15,1001,1001,1001,1001,35,12,22,22,31,34,1001,1001,304,1001,22,17,12,13,25,1001,1001,401,1001,1001,15,14,104,1001,1001,1001,1001,57,55,14,18,1001,1001,1001,1001,1001,15,23,16,783,19,1001,1001,1001,1001,18,23,21,27,21,124,1001,1001,20,17,27,15,15,36,1001,1001,1001,17,1001,18,26,22,24,1001,1001,1001,26,14,15,13,145,15,28,1001,1001,1001,1001,14,68,13,37,946,1001,1001,38,20,16,15,16,16,13,1001,1001,20,15,15,15,17,115,1001,1001,1001,1001,15,20,17,13,19,1001,1001,1001,20,20,17,23,16,190,1001,1001,1001,17,17,15,30,1001,13,1001,1001,1001,17,15,1001,13,13,13,16,1001,1001,1001,20,1001,13,15,39,100,1001,1001,1001,17,14,27,91,72,1001,1001,1001,503,33,14,15,13,23,1001,1001,1001,32,1001,290,14,25,1001,1001,1001,1001,1001,280,12,16,25,16,16,1001,1001,23,50,15,18,15,1001,1001,1001,1001,1001,14,221,109,250,13,19,1001,1001,11,18,48,19,28,16,1001,1001,1001,1001,37,1001,16,15,22,1001,1001,1001,14,15,1001,46,201,61,52,1001,1001,1001,97,169,105,33,48,46,1001,1001,20,1001,25,15,16,1001,1001,1001,1001,17,28,13,52,23,346,1001,1001,1001,17,14,1001,13,13,1001,1001,1001,1001,1001,27,17,12,67,15,1001,1001,1001,1001,27,14,31,16,16,31,1001,1001,14,14,14,15,26,1001,202,1001,1001,14,50,27,40,14,16,16,1001,1001,1001,1001,17,16,15,16,16,1001,1001,1001,14,15,15,15,73,19,1001,1001,241,1001,15,20,19,16,19,1001,1001,76,17,42,16,16,16,1001,1001,1001,1001,14,21,15,21,64,1001,1001,1001,296,23,14,23,13,19,19,1001,1001,1001,18,26,1001,16,96,34,1001,1001,38,67,14,18,15,16,16,1001,1001,1001,21,23,23,15,33,1001,1001,1001,53,386,23,17,1001,13,19,1001,1001,1001,17,17,12,67,16,1001,1001,1001,1001,17,419,15,78,1001,13,1001,1001,14,43,14,59,1001,1001,233,1001,1001,166,52,17,14,16,1001,31,1001,1001,38,26,16,16,16,16,1001,1001,1001,17,53,15,15,23,40,1001,1001,1001,107,23,136,68,19,15,1001,1001,1001,1001,38,20,16,98,15,28,1001,1001,1001,312,14,13,1001,67,1001,1001,1001,23,26,217,43,34,13,13,1001,1001,239,1001,27,35,17,39,62,1001,1001,1001,17,32,21,16,1001,1001,1001,1001,47,14,23,36,18,1001,56,1001,1001,1001,35,22,82,1001,16,1001,1001,1001,23,17,98,15,16,16,16,1001,1001,1001,85,19,15,21,39,1001,1001,1001,1001,132,31,1001,13,19,1001,1001,1001,1001,220,17,40,16,21,109,1001,1001,38,322,16,14,15,21,1001,1001,1001,46,17,22,21,843,348,1001,1001,1001,1001,15,18,20,17,13,28,1001,1001,1001,739,98,15,15,15,28,1001,1001,1001,101,64,15,28,1001,13,1001,1001,37,12,15,90,13,13,13,1001,1001,1001,15,17,17,13,28,22,1001,1001,1001,14,17,363,51,16,1001,1001,1001,20,287,14,18,39,13,29,1001,1001,17,367,16,17,14,1001,16,1001,1001,935,38,21,13,16,15,16,1001,1001,184,17,14,19,15,39,1001,1001,1001,1001,366,55,39,12,21,13,1001,1001,917,82,416,14,17,16,1001,1001,1001,1001,14,14,14,18,198,1001,1001,1001,319,14,17,16,46,19,385,1001,1001,14,18,15,19,35,16,157,1001,1001,212,1001,14,15,18,18,16,1001,1001,17,24,118,18,23,30,1001,1001,1001,1001,17,118,22,13,42,1001,1001,1001,1001,1001,17,17,13,22,1001,1001,1001,1001,147,45,14,19,290,1001,1001,1001,25,17,20,25,1001,333,1001,1001,1001,97,158,15,1001,21,40,1001,1001,1001,548,20,17,24,16,16,1001,1001,1001,17,17,17,15,30,395,1001,1001,1001,17,23,40,15,17,56,16,1001,1001,14,1001,822,24,15,28,1001,1001,1001,131,14,14,21,22,1001,404,1001,1001,101,1001,23,16,16,13,1001,1001,1001,1001,392,15,17,1001,19,1001,1001,1001,431,20,20,18,19,45,1001,1001,1001,1001,17,17,16,21,1001,1001,1001,1001,1001,15,16,61,61,77,559,1001,1001,1001,27,20,21,13,16,148,1001,1001,1001,83,19,19,17,57,1001,1001,1001,29,392,17,650,62,31,92,1001,1001,44,1001,15,26,40,40,1001,1001,1001,743,33,14,17,19,20,1001,1001,1001,17,17,17,15,1001,16,1001,1001,1001,215,15,15,15,40,53,38,1001,1001,1001,15,1001,1001,18,15,28,1001,1001,1001,121,17,14,19,16,520,1001,1001,26,663,15,1001,22,372,13,1001,1001,44,35,117,1001,14,40,1001,1001,1001,1001,20,108,22,16,43,1001,1001,1001,1001,14,15,16,22,80,1001,1001,1001,1001,18,65,15,52,27,44,1001,1001,1001,1001,1001,24,17,36,16,1001,1001,17,17,12,15,17,39,1001,1001,1001,83,1001,17,1001,16,19,935,1001,1001,20,14,18,40,98,18,32,1001,1001,1001,1001,39,14,14,16,1001,1001,1001,341,17,672,16,16,16,1001,1001,1001,770,15,18,15,1001,1001,1001,1001,1001,95,18,17,65,15,18,22,1001,1001,17,17,17,27,16,1001,1001,1001,1001,17,46,13,21,67,1001,1001,1001,1001,845,21,61,61,45,66,28,1001,1001,1001,17,14,17,1001,16,25,1001,1001,1001,17,17,15,28,16,31,1001,1001,58,17,65,18,17,1001,1001,1001,1001,35,1001,17,17,13,43,26,1001,1001,17,17,17};

int Main()
{
    scanf("%d",&x);
    if(biao[x]>L) return printf("%d %d %d\n",L+1,L+1,L+1),0;
    for(int i=-L;i<=L;i++){
    	int j=biao[x];
    	int p=x-j*j*j-i*i*i;
    	double l=pow(abs(p),1.0/3);
    	if(p<0) l=-l;
    	int o=l;
    	if(o*o*o==p){
    	   	return printf("%d %d %d\n",i,j,o),0;
		}
	    o=l+1;
    	if(o*o*o==p){
    		return printf("%d %d %d\n",i,j,o),0;
		}
		o=l-1;
    	if(o*o*o==p){
    		return printf("%d %d %d\n",i,j,o),0;
		}
		j=-biao[x];
    	p=x-j*j*j-i*i*i;
    	l=pow(abs(p),1.0/3);
    	if(p<0) l=-l;
    	o=l;
    	if(o*o*o==p){
    	   	return printf("%d %d %d\n",i,j,o),0;
		}
	    o=l+1;
    	if(o*o*o==p){
    		return printf("%d %d %d\n",i,j,o),0;
		}
		o=l-1;
    	if(o*o*o==p){
    		return printf("%d %d %d\n",i,j,o),0;
		}
	}
	puts("写挂了");
	return 0;
}
int main()
{
    int Case=1;
    scanf("%d%d",&L,&Case);
    while(Case--) Main();
	return 0;
}