学步园

An Awful Problem

Time Limit:1 Second      Memory Limit:32768 KB

In order to encourage Hiqivenfin to study math, his mother gave him a sweet candy when the day of the month was a prime number. Hiqivenfin was happy with that. But several days later, his mother modified the rule so that he could get a candy only when the day of the month was a prime number and the month was also a prime number. He felt a bit upset because he could get fewer candies. What's worse, his mother changed the rule again and he had to answer a question before he could get a candy in those days. The question was that how many candies he could get in the given time interval. Hiqivenfin wanted to cry and asked you for help. He promised to give you half of a candy if you could help him to solve this problem.

Input

There are multiple test cases. The first line of input is an integer T (0 < T <= 50), indicating the number of test cases. Then T test cases follow. The i-th line of the next T lines contains two dates, the day interval of the question. The format of the date is "yyyy mm dd". You can assume both dates are valid. Hiqivenfin was born at 1000-01-01 and would not die after 2999-12-31, so the queries are all in this interval.

Hiqivenfin didn't seem to be an earthman, but the calendar was the same as that we usually use. That is to say, you need to identify leap years, where February has 29 days. In the Gregorian calendar, leap years occur in years exactly divisible by four. So, 1993, 1994, and 1995 are not leap years, while 1992 and 1996 are leap years. Additionally, the years ending with 00 are leap years only if they are divisible by 400. So, 1700, 1800, 1900, 2100, and 2200 are not leap years, while 1600, 2000, and 2400 are leap years.

Output

Output the number of candies Hiqivenfin could get in the time interval. Both sides of the interval are inclusive.

Sample Input

2

1000 01 01 1000 01 31

2000 02 01 2000 03 01

Sample Output

0

10

省赛参加的晚，这题没交上，不知道能AC不....

import java.util.*;<br /> public class ZOJ4 {<br /> public static void main(String[] args){<br /> Scanner cin=new Scanner(System.in);<br /> int t=cin.nextInt();<br /> while(t!=0){<br /> t--;<br /> int sum=0;<br /> int yy1=cin.nextInt();<br /> int mm1=cin.nextInt();<br /> int dd1=cin.nextInt();<br /> int yy2=cin.nextInt();<br /> int mm2=cin.nextInt();<br /> int dd2=cin.nextInt();<br /> if(yy1==yy2){<br /> if(mm1==mm2){<br /> if(!isPrimes(mm1)) sum=0;<br /> else{<br /> if(dd1==dd2){<br /> if(!isPrimes(dd1)) sum=0;<br /> else sum=1;<br /> }<br /> else{<br /> sum=primes(dd1,dd2,sum);<br /> if(dd1==1) sum--;<br /> }<br /> }<br /> }<br /> else {<br /> for(int temp=mm1+1;temp<mm2;temp++){</p> <p> if(temp==2){<br /> if(year(yy1)) sum+=10;<br /> else sum+=9;<br /> }<br /> if(temp==3||temp==5||temp==7) sum+=11;<br /> if(temp==11) sum+=10;<br /> }<br /> if(isPrimes(mm1)){<br /> if(mm1==2){<br /> if(year(yy1)){<br /> sum=primes(dd1,29,sum);<br /> if(dd1==1) sum--;<br /> }<br /> else{<br /> sum=primes(dd1,28,sum);<br /> if(dd1==1) sum--;<br /> }<br /> }<br /> if(mm1==3||mm1==5||mm1==7){<br /> sum=primes(dd1,31,sum);<br /> if(dd1==1) sum--;<br /> }<br /> if(mm1==11){<br /> sum=primes(dd1,30,sum);<br /> if(dd1==1) sum--;<br /> }</p> <p> }<br /> if(isPrimes(mm2)){<br /> sum=primes(2,dd2,sum);<br /> }<br /> }<br /> }<br /> else{<br /> for(int temp1=yy1+1;temp1<yy2;temp1++){<br /> if(year(temp1)) sum+=53;<br /> else sum+=52;<br /> }<br /> sum+=md1(mm1+1,sum); //求出mm1+1月~12月之间质数月质数日个数//<br /> if(mm1+1<=2)<br /> if(year(yy1))<br /> sum++;<br /> sum+=md2(mm2-1,sum); //求出1月到mm2-1月之间质数月质数日个数//<br /> if(mm2-1>=2)<br /> if(year(yy2))<br /> sum++;<br /> if(!isPrimes(mm1)){<br /> if(mm1==2){<br /> if(year(yy1)){<br /> sum=primes(dd1,29,sum);<br /> if(dd1==1) sum--;<br /> }<br /> else{<br /> sum=primes(dd1,28,sum);<br /> if(dd1==1) sum--;<br /> }<br /> }<br /> if(mm1==3||mm1==5||mm1==7){<br /> sum=primes(dd1,31,sum);<br /> if(dd1==1) sum--;<br /> }<br /> if(mm1==11){<br /> sum=primes(dd1,30,sum);<br /> if(dd1==1) sum--;<br /> }<br /> }<br /> if(!isPrimes(mm2)) sum=primes(2,dd2,sum);<br /> }<br /> System.out.println(sum);<br /> }<br /> }<br /> public static int md1(int m,int sum){ //求出mm1+1月~12月之间质数月质数日个数<br /> switch(m){<br /> case 1:<br /> case 2: sum+=52;break;<br /> case 3: sum+=43;break;<br /> case 4:<br /> case 5: sum+=32;break;<br /> case 6:<br /> case 7: sum+=21;break;<br /> case 8:<br /> case 9:<br /> case 10:<br /> case 11: sum+=11;break;<br /> case 12: sum+=0;break;<br /> }<br /> return sum;<br /> }<br /> public static int md2(int m,int sum){ //求出1月到mm2-1月之间质数月质数日个数<br /> switch(m){<br /> case 1: sum+=0;break;<br /> case 2: sum+=9;break;<br /> case 3:<br /> case 4: sum+=20;break;<br /> case 5:<br /> case 6: sum+=31;break;<br /> case 7:<br /> case 8:<br /> case 9:<br /> case 10: sum+=42;break;<br /> case 11:<br /> case 12: sum+=52;break;<br /> }<br /> return sum;<br /> }<br /> public static int primes(int a,int b,int sum){//求出任意两个数之间的质数个数<br /> int i,j;<br /> for (i = a; i <= b; i++ ) {<br /> for (j = 2; j <= i / 2; j++ ) {<br /> if (i % j == 0)<br /> break;<br /> }<br /> if (j > i / 2)<br /> sum++;<br /> }<br /> return sum;<br /> }<br /> public static boolean isPrimes(int x) {<br /> if (x <= 7) {<br /> if (x==2||x==3||x==5||x==7) return true;<br /> else return false;<br /> }<br /> int c = 7;<br /> if (x % 2 == 0) return false;<br /> if (x % 3 == 0) return false;<br /> if (x % 5 == 0) return false;<br /> int end = (int) Math.sqrt(x);<br /> while (c <= end){<br /> if (x % c == 0){<br /> return false;<br /> }<br /> c += 4;<br /> if (x % c == 0){<br /> return false;<br /> }<br /> c += 2;<br /> if (x % c == 0) {<br /> return false;<br /> }<br /> c += 4;<br /> if (x % c == 0) {<br /> return false;<br /> }<br /> c += 2;<br /> if (x % c == 0) {<br /> return false;<br /> }<br /> c += 4;<br /> if (x % c == 0) {<br /> return false;<br /> }<br /> c += 6;<br /> if (x % c == 0) {<br /> return false;<br /> }<br /> c += 2;<br /> if (x % c == 0) {<br /> return false;<br /> }<br /> c += 6;<br /> }<br /> return true;<br /> }<br /> public static boolean year(int year){<br /> boolean flag=false;<br /> if((year%4==0)&&((year%100!=0)||(year%400==0))){<br /> flag=true;<br /> }<br /> return flag;<br /> }<br /> }