#include <iostream>
#include <iomanip>
using namespace std;
 
// Let's see if this works !!!
// (After all, I might have screwed up somewhere, so there's no guarantees!)
 
unsigned int sqrtOfLong(unsigned long x) {
  // inspired by https://w...content-available-to-author-only...e.com/watch?v=haaCoVrGd6k
  unsigned long leftover     = x;
  unsigned long leftoverStep = 0UL;
  unsigned long result       = 0UL;
  unsigned long resultStep   = 0x40000000UL;
  do {
    leftoverStep >>= 1;    
    result       >>= 1;
    if ((leftoverStep + resultStep) <= leftover) {
      leftoverStep += resultStep;
      leftover     -= leftoverStep;
      result       += resultStep;
      leftoverStep += resultStep;
    }
    resultStep   >>= 2;
  } while (resultStep);
  return ((unsigned int)result);
}
 
int main() {
	unsigned long ok = 0;
	unsigned long ng = 0;
 
	for (unsigned long i = 0; i <= 30; i++) {
	  unsigned long qu = i * i;
	  unsigned int  rt = sqrtOfLong(qu);  
      cout << setw(5) << i << "  " << setw(5) << qu << "  " << setw(5) << rt << "\n";
      if (i == rt) {
      	ok++;
      }
      else {
      	ng++;
      }
      cout << "\n";
      qu += (2*i);
      rt = sqrtOfLong(qu);  
      cout << setw(5) << i << "  " << setw(5) << qu << "  " << setw(5) << rt << "\n";
      if (i == rt) {
      	ok++;
      }
      else {
      	ng++;
      }
	}
	cout << "\n";
	cout << "OK: " << ok << "\n";
	cout << "NG: " << ng << "\n";
 
	// your code goes here
	return 0;
}

I2luY2x1ZGUgPGlvc3RyZWFtPgojaW5jbHVkZSA8aW9tYW5pcD4KdXNpbmcgbmFtZXNwYWNlIHN0ZDsKCi8vIExldCdzIHNlZSBpZiB0aGlzIHdvcmtzICEhIQovLyAoQWZ0ZXIgYWxsLCBJIG1pZ2h0IGhhdmUgc2NyZXdlZCB1cCBzb21ld2hlcmUsIHNvIHRoZXJlJ3Mgbm8gZ3VhcmFudGVlcyEpCgp1bnNpZ25lZCBpbnQgc3FydE9mTG9uZyh1bnNpZ25lZCBsb25nIHgpIHsKICAvLyBpbnNwaXJlZCBieSBodHRwczovL3cuLi5jb250ZW50LWF2YWlsYWJsZS10by1hdXRob3Itb25seS4uLmUuY29tL3dhdGNoP3Y9aGFhQ29WckdkNmsKICB1bnNpZ25lZCBsb25nIGxlZnRvdmVyICAgICA9IHg7CiAgdW5zaWduZWQgbG9uZyBsZWZ0b3ZlclN0ZXAgPSAwVUw7CiAgdW5zaWduZWQgbG9uZyByZXN1bHQgICAgICAgPSAwVUw7CiAgdW5zaWduZWQgbG9uZyByZXN1bHRTdGVwICAgPSAweDQwMDAwMDAwVUw7CiAgZG8gewogICAgbGVmdG92ZXJTdGVwID4+PSAxOyAgICAKICAgIHJlc3VsdCAgICAgICA+Pj0gMTsKICAgIGlmICgobGVmdG92ZXJTdGVwICsgcmVzdWx0U3RlcCkgPD0gbGVmdG92ZXIpIHsKICAgICAgbGVmdG92ZXJTdGVwICs9IHJlc3VsdFN0ZXA7CiAgICAgIGxlZnRvdmVyICAgICAtPSBsZWZ0b3ZlclN0ZXA7CiAgICAgIHJlc3VsdCAgICAgICArPSByZXN1bHRTdGVwOwogICAgICBsZWZ0b3ZlclN0ZXAgKz0gcmVzdWx0U3RlcDsKICAgIH0KICAgIHJlc3VsdFN0ZXAgICA+Pj0gMjsKICB9IHdoaWxlIChyZXN1bHRTdGVwKTsKICByZXR1cm4gKCh1bnNpZ25lZCBpbnQpcmVzdWx0KTsKfQoKaW50IG1haW4oKSB7Cgl1bnNpZ25lZCBsb25nIG9rID0gMDsKCXVuc2lnbmVkIGxvbmcgbmcgPSAwOwoJCglmb3IgKHVuc2lnbmVkIGxvbmcgaSA9IDA7IGkgPD0gMzA7IGkrKykgewoJICB1bnNpZ25lZCBsb25nIHF1ID0gaSAqIGk7CgkgIHVuc2lnbmVkIGludCAgcnQgPSBzcXJ0T2ZMb25nKHF1KTsgIAogICAgICBjb3V0IDw8IHNldHcoNSkgPDwgaSA8PCAiICAiIDw8IHNldHcoNSkgPDwgcXUgPDwgIiAgIiA8PCBzZXR3KDUpIDw8IHJ0IDw8ICJcbiI7CiAgICAgIGlmIChpID09IHJ0KSB7CiAgICAgIAlvaysrOwogICAgICB9CiAgICAgIGVsc2UgewogICAgICAJbmcrKzsKICAgICAgfQogICAgICBjb3V0IDw8ICJcbiI7CiAgICAgIHF1ICs9ICgyKmkpOwogICAgICBydCA9IHNxcnRPZkxvbmcocXUpOyAgCiAgICAgIGNvdXQgPDwgc2V0dyg1KSA8PCBpIDw8ICIgICIgPDwgc2V0dyg1KSA8PCBxdSA8PCAiICAiIDw8IHNldHcoNSkgPDwgcnQgPDwgIlxuIjsKICAgICAgaWYgKGkgPT0gcnQpIHsKICAgICAgCW9rKys7CiAgICAgIH0KICAgICAgZWxzZSB7CiAgICAgIAluZysrOwogICAgICB9Cgl9Cgljb3V0IDw8ICJcbiI7Cgljb3V0IDw8ICJPSzogIiA8PCBvayA8PCAiXG4iOwoJY291dCA8PCAiTkc6ICIgPDwgbmcgPDwgIlxuIjsKCQoJLy8geW91ciBjb2RlIGdvZXMgaGVyZQoJcmV0dXJuIDA7Cn0=