시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
5 초 128 MB 82 16 5 10.000%

문제

양의 정수 m과 소수 p, 그리고 p로 나누었을 때의 나머지 a가 주어진다.

이때, nn + nm을 p로 나눈 나머지가 a가 되는 n이 존재하는지를 구하고, 존재하면 n을 구하는 프로그램을 작성하시오.

입력

입력은 여러 개의 테스트 케이스로 이루어져 있다. 첫째 줄에는 테스트 케이스의 개수 d (1 ≤ d ≤ 300)가 주어진다.

각 테스트 케이스는 한 줄로 이루어져 있으며, 세 정수 p, a, m이 주어진다. (2 ≤ p ≤ 109, 0 ≤ a < p, 1 ≤ m ≤ 20, m < p) p는 항상 소수이다. 

출력

문제의 조건에 해당하는 n < 101000이 존재하면, "TAK n"을 출력하고, 존재하지 않는 경우에는 "NIE"를 출력한다.

예제 입력 1

2
11 3 1
11 8 2

예제 출력 1

TAK 567
TAK 2
W3sicHJvYmxlbV9pZCI6Ijc5MzYiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJOXHVjNzU4IFx1Yzg3NFx1YzdhYyIsImRlc2NyaXB0aW9uIjoiPHA+XHVjNTkxXHVjNzU4IFx1YzgxNVx1YzIxOCBtXHVhY2ZjIFx1YzE4Y1x1YzIxOCBwLCBcdWFkZjhcdWI5YWNcdWFjZTAgcFx1Yjg1YyBcdWIwOThcdWIyMDRcdWM1YzhcdWM3NDQgXHViNTRjXHVjNzU4IFx1YjA5OFx1YmEzOFx1YzljMCBhXHVhYzAwIFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHVjNzc0XHViNTRjLCBuPHN1cD5uPFwvc3VwPiArIG48c3VwPm08XC9zdXA+XHVjNzQ0IHBcdWI4NWMgXHViMDk4XHViMjA4IFx1YjA5OFx1YmEzOFx1YzljMFx1YWMwMCBhXHVhYzAwIFx1YjQxOFx1YjI5NCBuXHVjNzc0Jm5ic3A7XHVjODc0XHVjN2FjXHVkNTU4XHViMjk0XHVjOWMwXHViOTdjIFx1YWQ2Y1x1ZDU1OFx1YWNlMCwgXHVjODc0XHVjN2FjXHVkNTU4XHViYTc0IG5cdWM3NDQgXHVhZDZjXHVkNTU4XHViMjk0IFx1ZDUwNFx1Yjg1Y1x1YWRmOFx1YjdhOFx1Yzc0NCBcdWM3OTFcdWMxMzFcdWQ1NThcdWMyZGNcdWM2MjQuPFwvcD5cclxuIiwiaW5wdXQiOiI8cD5cdWM3ODVcdWI4MjVcdWM3NDAgXHVjNWVjXHViN2VjIFx1YWMxY1x1Yzc1OCBcdWQxNGNcdWMyYTRcdWQyYjggXHVjZjAwXHVjNzc0XHVjMmE0XHViODVjIFx1Yzc3NFx1YjhlOFx1YzViNFx1YzgzOCBcdWM3ODhcdWIyZTQuIFx1Y2NhYlx1YzlmOCBcdWM5MDRcdWM1ZDBcdWIyOTQgXHVkMTRjXHVjMmE0XHVkMmI4IFx1Y2YwMFx1Yzc3NFx1YzJhNFx1Yzc1OCBcdWFjMWNcdWMyMTggZCAoMSAmbGU7IGQgJmxlOyAzMDApXHVhYzAwIFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHVhYzAxIFx1ZDE0Y1x1YzJhNFx1ZDJiOCBcdWNmMDBcdWM3NzRcdWMyYTRcdWIyOTQgXHVkNTVjIFx1YzkwNFx1Yjg1YyBcdWM3NzRcdWI4ZThcdWM1YjRcdWM4MzggXHVjNzg4XHVjNzNjXHViYTcwLCBcdWMxMzggXHVjODE1XHVjMjE4IHAsIGEsIG1cdWM3NzQgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiAoMiAmbGU7IHAgJmxlOyAxMDxzdXA+OTxcL3N1cD4sIDAgJmxlOyBhICZsdDsgcCwgMSAmbGU7IG0gJmxlOyAyMCwgbSAmbHQ7IHApIHBcdWIyOTQgXHVkNTZkXHVjMGMxIFx1YzE4Y1x1YzIxOFx1Yzc3NFx1YjJlNC4mbmJzcDs8XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5cdWJiMzhcdWM4MWNcdWM3NTggXHVjODcwXHVhYzc0XHVjNWQwIFx1ZDU3NFx1YjJmOVx1ZDU1OFx1YjI5NCBuICZsdDsgMTA8c3VwPjEwMDA8XC9zdXA+XHVjNzc0IFx1Yzg3NFx1YzdhY1x1ZDU1OFx1YmE3NCwgJnF1b3Q7VEFLIG4mcXVvdDtcdWM3NDQgXHVjZDljXHViODI1XHVkNTU4XHVhY2UwLCBcdWM4NzRcdWM3YWNcdWQ1NThcdWM5YzAgXHVjNTRhXHViMjk0IFx1YWNiZFx1YzZiMFx1YzVkMFx1YjI5NCAmcXVvdDtOSUUmcXVvdDtcdWI5N2MgXHVjZDljXHViODI1XHVkNTVjXHViMmU0LjxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjAiLCJwcm9ibGVtX2xhbmdfY29kZSI6Ilx1ZDU1Y1x1YWQ2ZFx1YzViNCJ9LHsicHJvYmxlbV9pZCI6Ijc5MzYiLCJwcm9ibGVtX2xhbmciOiIzIiwidGl0bGUiOiJJc3RuaWVuaWUgTiIsImRlc2NyaXB0aW9uIjoiPHA+RGFuYSBqZXN0IGxpY3piYSBkb2RhdG5pYSBtLCBsaWN6YmEgcGllcndzemEgcCBvcmF6IGxpY3piYSBhIGJcdTAxMTlkXHUwMTA1Y2EgcmVzenRcdTAxMDUgeiBkemllbGVuaWEgbW9kdWxvIHAuIE5hbGVcdTAxN2N5IHNwcmF3ZHppXHUwMTA3LCBjenkgaXN0bmllamUgdGFrYSBkb2RhdG5pYSBsaWN6YmEgY2FcdTAxNDJrb3dpdGEgbiwgZGxhIGt0Jm9hY3V0ZTtyZWogd3lyYVx1MDE3Y2VuaWUgbjxzdXA+bjxcL3N1cD4gK248c3VwPm08XC9zdXA+IGRhamUgcmVzenRcdTAxMTkgYSB6IGR6aWVsZW5pYSBwcnpleiBwLCBpIGplXHUwMTdjZWxpIHRhaywgdG8gcG9kYVx1MDEwNyBwcnp5a1x1MDE0MmFkIHRha2llZ28gbi48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlcgcGllcndzemVqIGxpbmlpIHdlalx1MDE1YmNpYSB6bmFqZHVqZSBzaVx1MDExOSBsaWN6YmEgbmF0dXJhbG5hIGQgKDEgJmxlOyBkICZsZTsgMzAwKSwgb2tyZVx1MDE1Ymxhalx1MDEwNWNhIGxpY3piXHUwMTE5IHRlc3Qmb2FjdXRlO3csIGt0Jm9hY3V0ZTtyeWNoIG9waXN5IHpuYWpkdWpcdTAxMDUgc2lcdTAxMTkgdyBrb2xlam55Y2ggbGluaWFjaC48XC9wPlxyXG5cclxuPHA+S2FcdTAxN2NkeSB0ZXN0IHNrXHUwMTQyYWRhIHNpXHUwMTE5IHogamVkbmVqIGxpbmlpLCB3IGt0Jm9hY3V0ZTtyZWogem5hamR1alx1MDEwNSBzaVx1MDExOSB0cnp5IGxpY3pieSBjYVx1MDE0Mmtvd2l0ZSBwLCBhIG9yYXogbSAoMiAmbGU7IHAgJmxlOyAxMDxzdXA+OTxcL3N1cD4sIDAgJmxlOyBhICZsdDsgcCwgMSAmbGU7IG0gJmxlOyAyMCwgbSAmbHQ7IHApLjxcL3A+XHJcblxyXG48cD5MaWN6YmEgcCB6YXdzemUgYlx1MDExOWR6aWUgbGljemJcdTAxMDUgcGllcndzelx1MDEwNS48XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5EbGEga2FcdTAxN2NkZWdvIHRlc3R1IG5hbGVcdTAxN2N5IHcgb3NvYm5laiBsaW5paSB3eXBpc2FcdTAxMDcgVEFLIG4gLCBqZVx1MDE3Y2VsaSBpc3RuaWVqZSBuICZsdDsgMTA8c3VwPjEwMDA8XC9zdXA+IHNwZVx1MDE0Mm5pYWpcdTAxMDVjZSBvcGlzYW5cdTAxMDUgd1x1MDE0MmFzbm9cdTAxNWJcdTAxMDcsIGx1YiBzYW1vIHNcdTAxNDJvd28gTklFIHcgcHJ6ZWNpd255bSBwcnp5cGFka3UuPFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMSIsInByb2JsZW1fbGFuZ19jb2RlIjoiXHVkM2Y0XHViNzgwXHViNGRjXHVjNWI0In1d