시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
5 초 128 MB 87 18 6 11.111%

문제

양의 정수 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+XHVjNzQ0IHBcdWI4NWMgXHViMDk4XHViMjA4IFx1YjA5OFx1YmEzOFx1YzljMFx1YWMwMCBhXHVhYzAwIFx1YjQxOFx1YjI5NCBcdWM1OTFcdWM3NTggXHVjODE1XHVjMjE4IG5cdWM3NzQmbmJzcDtcdWM4NzRcdWM3YWNcdWQ1NThcdWIyOTRcdWM5YzBcdWI5N2MgXHVhZDZjXHVkNTU4XHVhY2UwLCBcdWM4NzRcdWM3YWNcdWQ1NThcdWJhNzQgblx1Yzc0NCBcdWFkNmNcdWQ1NThcdWIyOTQgXHVkNTA0XHViODVjXHVhZGY4XHViN2E4XHVjNzQ0IFx1Yzc5MVx1YzEzMVx1ZDU1OFx1YzJkY1x1YzYyNC48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlx1Yzc4NVx1YjgyNVx1Yzc0MCBcdWM1ZWNcdWI3ZWMgXHVhYzFjXHVjNzU4IFx1ZDE0Y1x1YzJhNFx1ZDJiOCBcdWNmMDBcdWM3NzRcdWMyYTRcdWI4NWMgXHVjNzc0XHViOGU4XHVjNWI0XHVjODM4IFx1Yzc4OFx1YjJlNC4gXHVjY2FiXHVjOWY4IFx1YzkwNFx1YzVkMFx1YjI5NCBcdWQxNGNcdWMyYTRcdWQyYjggXHVjZjAwXHVjNzc0XHVjMmE0XHVjNzU4IFx1YWMxY1x1YzIxOCBkICgxICZsZTsgZCAmbGU7IDMwMClcdWFjMDAgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWFjMDEgXHVkMTRjXHVjMmE0XHVkMmI4IFx1Y2YwMFx1Yzc3NFx1YzJhNFx1YjI5NCBcdWQ1NWMgXHVjOTA0XHViODVjIFx1Yzc3NFx1YjhlOFx1YzViNFx1YzgzOCBcdWM3ODhcdWM3M2NcdWJhNzAsIFx1YzEzOCBcdWM4MTVcdWMyMTggcCwgYSwgbVx1Yzc3NCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuICgyICZsZTsgcCAmbGU7IDEwPHN1cD45PFwvc3VwPiwgMCAmbGU7IGEgJmx0OyBwLCAxICZsZTsgbSAmbGU7IDIwLCBtICZsdDsgcCkgcFx1YjI5NCBcdWQ1NmRcdWMwYzEgXHVjMThjXHVjMjE4XHVjNzc0XHViMmU0LiZuYnNwOzxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPlx1YmIzOFx1YzgxY1x1Yzc1OCBcdWM4NzBcdWFjNzRcdWM1ZDAgXHVkNTc0XHViMmY5XHVkNTU4XHViMjk0IG4gJmx0OyAxMDxzdXA+MTAwMDxcL3N1cD5cdWM3NzQgXHVjODc0XHVjN2FjXHVkNTU4XHViYTc0LCAmcXVvdDtUQUsgbiZxdW90O1x1Yzc0NCBcdWNkOWNcdWI4MjVcdWQ1NThcdWFjZTAsIFx1Yzg3NFx1YzdhY1x1ZDU1OFx1YzljMCBcdWM1NGFcdWIyOTQgXHVhY2JkXHVjNmIwXHVjNWQwXHViMjk0ICZxdW90O05JRSZxdW90O1x1Yjk3YyBcdWNkOWNcdWI4MjVcdWQ1NWNcdWIyZTQuPFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMCIsInByb2JsZW1fbGFuZ19jb2RlIjoiXHVkNTVjXHVhZDZkXHVjNWI0In0seyJwcm9ibGVtX2lkIjoiNzkzNiIsInByb2JsZW1fbGFuZyI6IjMiLCJ0aXRsZSI6IklzdG5pZW5pZSBOIiwiZGVzY3JpcHRpb24iOiI8cD5EYW5hIGplc3QgbGljemJhIGRvZGF0bmlhIG0sIGxpY3piYSBwaWVyd3N6YSBwIG9yYXogbGljemJhIGEgYlx1MDExOWRcdTAxMDVjYSByZXN6dFx1MDEwNSB6IGR6aWVsZW5pYSBtb2R1bG8gcC4gTmFsZVx1MDE3Y3kgc3ByYXdkemlcdTAxMDcsIGN6eSBpc3RuaWVqZSB0YWthIGRvZGF0bmlhIGxpY3piYSBjYVx1MDE0Mmtvd2l0YSBuLCBkbGEga3Qmb2FjdXRlO3JlaiB3eXJhXHUwMTdjZW5pZSBuPHN1cD5uPFwvc3VwPiArbjxzdXA+bTxcL3N1cD4gZGFqZSByZXN6dFx1MDExOSBhIHogZHppZWxlbmlhIHByemV6IHAsIGkgamVcdTAxN2NlbGkgdGFrLCB0byBwb2RhXHUwMTA3IHByenlrXHUwMTQyYWQgdGFraWVnbyBuLjxcL3A+XHJcbiIsImlucHV0IjoiPHA+VyBwaWVyd3N6ZWogbGluaWkgd2VqXHUwMTViY2lhIHpuYWpkdWplIHNpXHUwMTE5IGxpY3piYSBuYXR1cmFsbmEgZCAoMSAmbGU7IGQgJmxlOyAzMDApLCBva3JlXHUwMTVibGFqXHUwMTA1Y2EgbGljemJcdTAxMTkgdGVzdCZvYWN1dGU7dywga3Qmb2FjdXRlO3J5Y2ggb3Bpc3kgem5hamR1alx1MDEwNSBzaVx1MDExOSB3IGtvbGVqbnljaCBsaW5pYWNoLjxcL3A+XHJcblxyXG48cD5LYVx1MDE3Y2R5IHRlc3Qgc2tcdTAxNDJhZGEgc2lcdTAxMTkgeiBqZWRuZWogbGluaWksIHcga3Qmb2FjdXRlO3JlaiB6bmFqZHVqXHUwMTA1IHNpXHUwMTE5IHRyenkgbGljemJ5IGNhXHUwMTQya293aXRlIHAsIGEgb3JheiBtICgyICZsZTsgcCAmbGU7IDEwPHN1cD45PFwvc3VwPiwgMCAmbGU7IGEgJmx0OyBwLCAxICZsZTsgbSAmbGU7IDIwLCBtICZsdDsgcCkuPFwvcD5cclxuXHJcbjxwPkxpY3piYSBwIHphd3N6ZSBiXHUwMTE5ZHppZSBsaWN6Ylx1MDEwNSBwaWVyd3N6XHUwMTA1LjxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPkRsYSBrYVx1MDE3Y2RlZ28gdGVzdHUgbmFsZVx1MDE3Y3kgdyBvc29ibmVqIGxpbmlpIHd5cGlzYVx1MDEwNyBUQUsgbiAsIGplXHUwMTdjZWxpIGlzdG5pZWplIG4gJmx0OyAxMDxzdXA+MTAwMDxcL3N1cD4gc3BlXHUwMTQybmlhalx1MDEwNWNlIG9waXNhblx1MDEwNSB3XHUwMTQyYXNub1x1MDE1Ylx1MDEwNywgbHViIHNhbW8gc1x1MDE0Mm93byBOSUUgdyBwcnplY2l3bnltIHByenlwYWRrdS48XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIxIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWQzZjRcdWI3ODBcdWI0ZGNcdWM1YjQifV0=