시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
5 초 128 MB 66 14 3 8.824%

문제

양의 정수 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+XHVjNzc0IFx1YjU0YywgbjxzdXA+bjxcL3N1cD4gKyBuPHN1cD5tPFwvc3VwPlx1Yzc0NCBwXHViODVjIFx1YjA5OFx1YjIwOCBcdWIwOThcdWJhMzhcdWM5YzBcdWFjMDAgYVx1YWMwMCBcdWI0MThcdWIyOTQgblx1Yzc3NCZuYnNwO1x1Yzg3NFx1YzdhY1x1ZDU1OFx1YjI5NFx1YzljMFx1Yjk3YyBcdWFkNmNcdWQ1NThcdWFjZTAsIFx1Yzg3NFx1YzdhY1x1ZDU1OFx1YmE3NCBuXHVjNzQ0IFx1YWQ2Y1x1ZDU1OFx1YjI5NCBcdWQ1MDRcdWI4NWNcdWFkZjhcdWI3YThcdWM3NDQgXHVjNzkxXHVjMTMxXHVkNTU4XHVjMmRjXHVjNjI0LjxcL3A+XHJcbiIsImlucHV0IjoiPHA+XHVjNzg1XHViODI1XHVjNzQwIFx1YzVlY1x1YjdlYyBcdWFjMWNcdWM3NTggXHVkMTRjXHVjMmE0XHVkMmI4IFx1Y2YwMFx1Yzc3NFx1YzJhNFx1Yjg1YyBcdWM3NzRcdWI4ZThcdWM1YjRcdWM4MzggXHVjNzg4XHViMmU0LiBcdWNjYWJcdWM5ZjggXHVjOTA0XHVjNWQwXHViMjk0IFx1ZDE0Y1x1YzJhNFx1ZDJiOCBcdWNmMDBcdWM3NzRcdWMyYTRcdWM3NTggXHVhYzFjXHVjMjE4IGQgKDEgJmxlOyBkICZsZTsgMzAwKVx1YWMwMCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YWMwMSBcdWQxNGNcdWMyYTRcdWQyYjggXHVjZjAwXHVjNzc0XHVjMmE0XHViMjk0IFx1ZDU1YyBcdWM5MDRcdWI4NWMgXHVjNzc0XHViOGU4XHVjNWI0XHVjODM4IFx1Yzc4OFx1YzczY1x1YmE3MCwgXHVjMTM4IFx1YzgxNVx1YzIxOCBwLCBhLCBtXHVjNzc0IFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gKDIgJmxlOyBwICZsZTsgMTA8c3VwPjk8XC9zdXA+LCAwICZsZTsgYSAmbHQ7IHAsIDEgJmxlOyBtICZsZTsgMjAsIG0gJmx0OyBwKSBwXHViMjk0IFx1ZDU2ZFx1YzBjMSBcdWMxOGNcdWMyMThcdWM3NzRcdWIyZTQuJm5ic3A7PFwvcD5cclxuIiwib3V0cHV0IjoiPHA+XHViYjM4XHVjODFjXHVjNzU4IFx1Yzg3MFx1YWM3NFx1YzVkMCBcdWQ1NzRcdWIyZjlcdWQ1NThcdWIyOTQgbiAmbHQ7IDEwPHN1cD4xMDAwPFwvc3VwPlx1Yzc3NCBcdWM4NzRcdWM3YWNcdWQ1NThcdWJhNzQsICZxdW90O1RBSyBuJnF1b3Q7XHVjNzQ0IFx1Y2Q5Y1x1YjgyNVx1ZDU1OFx1YWNlMCwgXHVjODc0XHVjN2FjXHVkNTU4XHVjOWMwIFx1YzU0YVx1YjI5NCBcdWFjYmRcdWM2YjBcdWM1ZDBcdWIyOTQgJnF1b3Q7TklFJnF1b3Q7XHViOTdjIFx1Y2Q5Y1x1YjgyNVx1ZDU1Y1x1YjJlNC48XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIwIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWQ1NWNcdWFkNmRcdWM1YjQifSx7InByb2JsZW1faWQiOiI3OTM2IiwicHJvYmxlbV9sYW5nIjoiMyIsInRpdGxlIjoiSXN0bmllbmllIE4iLCJkZXNjcmlwdGlvbiI6IjxwPkRhbmEgamVzdCBsaWN6YmEgZG9kYXRuaWEgbSwgbGljemJhIHBpZXJ3c3phIHAgb3JheiBsaWN6YmEgYSBiXHUwMTE5ZFx1MDEwNWNhIHJlc3p0XHUwMTA1IHogZHppZWxlbmlhIG1vZHVsbyBwLiBOYWxlXHUwMTdjeSBzcHJhd2R6aVx1MDEwNywgY3p5IGlzdG5pZWplIHRha2EgZG9kYXRuaWEgbGljemJhIGNhXHUwMTQya293aXRhIG4sIGRsYSBrdCZvYWN1dGU7cmVqIHd5cmFcdTAxN2NlbmllIG48c3VwPm48XC9zdXA+ICtuPHN1cD5tPFwvc3VwPiBkYWplIHJlc3p0XHUwMTE5IGEgeiBkemllbGVuaWEgcHJ6ZXogcCwgaSBqZVx1MDE3Y2VsaSB0YWssIHRvIHBvZGFcdTAxMDcgcHJ6eWtcdTAxNDJhZCB0YWtpZWdvIG4uPFwvcD5cclxuIiwiaW5wdXQiOiI8cD5XIHBpZXJ3c3plaiBsaW5paSB3ZWpcdTAxNWJjaWEgem5hamR1amUgc2lcdTAxMTkgbGljemJhIG5hdHVyYWxuYSBkICgxICZsZTsgZCAmbGU7IDMwMCksIG9rcmVcdTAxNWJsYWpcdTAxMDVjYSBsaWN6Ylx1MDExOSB0ZXN0Jm9hY3V0ZTt3LCBrdCZvYWN1dGU7cnljaCBvcGlzeSB6bmFqZHVqXHUwMTA1IHNpXHUwMTE5IHcga29sZWpueWNoIGxpbmlhY2guPFwvcD5cclxuXHJcbjxwPkthXHUwMTdjZHkgdGVzdCBza1x1MDE0MmFkYSBzaVx1MDExOSB6IGplZG5laiBsaW5paSwgdyBrdCZvYWN1dGU7cmVqIHpuYWpkdWpcdTAxMDUgc2lcdTAxMTkgdHJ6eSBsaWN6YnkgY2FcdTAxNDJrb3dpdGUgcCwgYSBvcmF6IG0gKDIgJmxlOyBwICZsZTsgMTA8c3VwPjk8XC9zdXA+LCAwICZsZTsgYSAmbHQ7IHAsIDEgJmxlOyBtICZsZTsgMjAsIG0gJmx0OyBwKS48XC9wPlxyXG5cclxuPHA+TGljemJhIHAgemF3c3plIGJcdTAxMTlkemllIGxpY3piXHUwMTA1IHBpZXJ3c3pcdTAxMDUuPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+RGxhIGthXHUwMTdjZGVnbyB0ZXN0dSBuYWxlXHUwMTdjeSB3IG9zb2JuZWogbGluaWkgd3lwaXNhXHUwMTA3IFRBSyBuICwgamVcdTAxN2NlbGkgaXN0bmllamUgbiAmbHQ7IDEwPHN1cD4xMDAwPFwvc3VwPiBzcGVcdTAxNDJuaWFqXHUwMTA1Y2Ugb3Bpc2FuXHUwMTA1IHdcdTAxNDJhc25vXHUwMTViXHUwMTA3LCBsdWIgc2FtbyBzXHUwMTQyb3dvIE5JRSB3IHByemVjaXdueW0gcHJ6eXBhZGt1LjxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjEiLCJwcm9ibGVtX2xhbmdfY29kZSI6Ilx1ZDNmNFx1Yjc4MFx1YjRkY1x1YzViNCJ9XQ==