public static void main(String Args[]) {
		int i = 0;
		long l = 0;

		for (i = 0; i < perfectarray.length; i++) {

			// l = i * i;
			// if (issquaredigitsquare(l)) {

			array[perfectarray[i]] = true;
			// System.out.println(perfectarray[i]);
			// System.out.print(",");
			// }
		}
		Scanner sr = new Scanner(System.in);
		int t = sr.nextInt();
		int answer = 0;
		long a = 0;
		long b = 0;
		long k = 0;
		while (t > 0) {

			a = (int) Math.sqrt(sr.nextLong());

			b = (int) Math.sqrt(sr.nextLong());

			for (k = a; k < (b + 1); k++) {

				if (array[(int) k] == true) {
					answer++;
				}
			}

			//answer++;
			System.out.println(answer);
			answer = 0;
			t--;
		}
		return;
	}