黑白點(diǎn)的匹配
 
Time Limit: 1 Seconds     Memory Limit: 32768 K

Total Submit:196     Accepted:41

--------------------------------------------------------------------------------
 
Description

設(shè)平面上分布著n個(gè)白點(diǎn)和n個(gè)黑點(diǎn)，每個(gè)點(diǎn)用一對(duì)坐標(biāo)（x, y）表示。一個(gè)黑點(diǎn)b=（xb,yb）支配一個(gè)白點(diǎn)w=(xw, yw)當(dāng)且僅當(dāng)xb>=xw和yb>=yw。若黑點(diǎn)b支配白點(diǎn)w，則黑點(diǎn)b和白點(diǎn)w可匹配（可形成一個(gè)匹配對(duì)）。在一個(gè)黑點(diǎn)最多只能與一個(gè)白點(diǎn)匹配，一個(gè)白點(diǎn)最多只能與一個(gè)黑點(diǎn)匹配的前提下，求n個(gè)白點(diǎn)和n個(gè)黑點(diǎn)的最大匹配對(duì)數(shù)。 

Input

輸入的第一行是一個(gè)正整數(shù)k，表示測(cè)試?yán)齻€(gè)數(shù)。接下來幾行是k個(gè)測(cè)試?yán)臄?shù)據(jù)，每個(gè)測(cè)試?yán)臄?shù)據(jù)由三行組成，其中第一行含1個(gè)正整數(shù)n；第二行含2n個(gè)實(shí)數(shù)xb1, yb1,xb2, yb2,…, xbn, ybn， (xbi, ybi)，i=1, 2, …, n表示n個(gè)黑點(diǎn)的坐標(biāo)；第三行含2n個(gè)實(shí)數(shù)xw1, yw1,xw2, yw2,…, xwn, ywn，(xwi, ywi)，i=1, 2, …, n表示n個(gè)白點(diǎn)的坐標(biāo)。同一行的實(shí)數(shù)之間用一個(gè)空格隔開。

Output

對(duì)于每個(gè)測(cè)試?yán)敵鲆恍?，含一個(gè)整數(shù)，表示n個(gè)白點(diǎn)和n個(gè)黑點(diǎn)的最大匹配對(duì)數(shù)。

Sample Input


1
3
5.0 3.0 5.0 -1.0 4.0 4.0
2.0 3.5 2.0 2.0 -2.0 -2.0

Sample Output


3
Source

算法設(shè)計(jì)作業(yè)