//Each non-edge node is visited at least twice so caching saves a ton of time
let triangleCache = {};
//Derived from the triangular number formula
let getRowOfIdx = idx => 
	Math.floor(-0.5 + Math.sqrt(0.25 + (2 * idx)));

let calculateMaxSum = (triangle, n=0) => {
  if (n >= triangle.length) return 0;
  if (triangleCache[n]) return triangleCache[n];
	
  let left = triangle[n] + calculateMaxSum(triangle, n + getRowOfIdx(n) + 1);
  let right = triangle[n] + calculateMaxSum(triangle, n + getRowOfIdx(n) + 2);
  triangleCache[n] = Math.max(left, right);
  return triangleCache[n];
}

function processData(input) {
    let data = input.split('\n');
    let numCases = data.shift();
    for (let i = 0; i < numCases; i++) {
      let numRows = data.shift();
      let rows = [];
      for (let j = 0; j < numRows; j++) {
        rows.push(...data.shift().split(' ').map(v => parseInt(v)));
      }
      console.log(calculateMaxSum(rows));
      triangleCache = {};
    }
}