I ran into the "Fair and Square" problem of Google's 2013 Code Jam ( https://code.google.com/codejam/contest/2270488/dashboard#s=p2&a=2 ) last night and ended up spending some time solving the large input 1 case in JS. Here's what I came up with (run it in node). It solves the 10^14 range in less than a millisecond on my end. Doesn't really work…

fairandsquare.js

var fs = require('fs');

var lines = fs.readFileSync('./C-large-practice-1.in', 'utf8').replace(/\r\n|\r/g,'\n').split('\n');

var time = Date.now();
var arr = palindromes(Math.pow(10,14));
time = Date.now() - time;

console.time("Total time for case solving");
for(var i = 0, ii = lines.shift(); i < ii; i++) {
  line = lines[i].split(' ');
  solver(line[0],line[1],i+1);
}
console.timeEnd("Total time for case solving");
console.log("Fair and Square calculation: "+time+"ms");

function solver(x,y,c) {
  var count = 0, cur;
  for(var i = 0, ii = arr.length; i < ii; i++) {
    cur = arr[i];
    if(cur >= x && cur <= y) count++;
  }
  console.log("Case #"+c+": "+count);
}

function palindromes(max) {
  var sq = Math.sqrt(max),
      i, ret = [], cur;
  for(i = 1 ;; i++) {
    if(pals(i,sq,ret)) {
      break;
    }
  } 
  return ret;
}

function pals(i,sq,out) {
  if(i < 4) {
    out.push(i*i);
  }

  var f = i.toString(3),
      b, arr, cur;
  
  var sm = sum(f);

  if(sm > 4) {
    return false;
  } else {
    arr = [];
    b = f.split('').reverse().join('');
    arr.push(f+b);
    arr.push(f+'0'+b);
    arr.push(f+'1'+b);
  }
  if(sm < 3) {
    arr.push(f+'2'+b);
  }

  for(var n = 0, nn = arr.length; n < nn; n++) {
    cur = +arr[n];
    if(cur > sq) {
      return cur;
    }
    out.push(cur*cur);
  }

  return 0;
}

function sum(str) {
  str = str.split('');
  var sm = 0;
  for(var i = 0, ii = str.length; i < ii; i++) {
    var s = +str[i];
    sm += (s === 2 ? 4 : s);
  }
  return sm;
}